All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1 Next

Displaying 1 – 20 of 27

Showing per page

Marches sur les arbres homogènes suivant une suite substitutive

Zhi-Xiong Wen, Zhi-Ying Wen (1992)

Journal de théorie des nombres de Bordeaux

Ce travail consiste à étudier les comportements des marches sur les arbres homogènes suivant la suite engendrée par une substitution. Dans la première partie, on étudie d’abord les marches sans orientation sur ℤ et on détermine complètement, d’après les propriétés combinatoires de la substitution, les conditions assurant que les marches sont bornées, récurrentes ou transientes. Comme corollaire, on obtient le comportement asymptotique des sommes partielles des coefficients de la suite substitutive....

Minimal 2-dominating sets in trees

Marcin Krzywkowski (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time 𝒪(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.

Minimum convex-cost tension problems on series-parallel graphs

Bruno Bachelet, Philippe Mahey (2003)

RAIRO - Operations Research - Recherche Opérationnelle

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in O ( m 3 ) operations.

Minimum convex-cost tension problems on series-parallel graphs

Bruno Bachelet, Philippe Mahey (2010)

RAIRO - Operations Research

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new aggregation method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in O(m3) operations.

Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

Dariusz Dereniowski (2009)

Discussiones Mathematicae Graph Theory

A vertex k-ranking of a simple graph is a coloring of its vertices with k colors in such a way that each path connecting two vertices of the same color contains a vertex with a bigger color. Consider the minimum vertex ranking spanning tree (MVRST) problem where the goal is to find a spanning tree of a given graph G which has a vertex ranking using the minimal number of colors over vertex rankings of all spanning trees of G. K. Miyata et al. proved in [NP-hardness proof and an approximation algorithm...

More on the complexity of cover graphs

Jaroslav Nešetřil, Vojtěch Rödl (1995)

Commentationes Mathematicae Universitatis Carolinae

In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.

Morphismes sturmiens et règles de Rauzy

Filippo Mignosi, Patrice Séébold (1993)

Journal de théorie des nombres de Bordeaux

Nous donnons une caractérisation complète de tous les morphismes binaires qui préservent les mots sturmiens et montrons que les mots infinis engendrés par ces morphismes sont rigides.

Morphisms fixing words associated with exchange of three intervals

Petr Ambrož, Zuzana Masáková, Edita Pelantová (2010)

RAIRO - Theoretical Informatics and Applications

We consider words coding exchange of three intervals with permutation (3,2,1), here called 3iet words. Recently, a characterization of substitution invariant 3iet words was provided. We study the opposite question: what are the morphisms fixing a 3iet word? We reveal a narrow connection of such morphisms and morphisms fixing Sturmian words using the new notion of amicability.

Currently displaying 1 – 20 of 27

Page 1 Next