Simple and efficient bilayer cross counting.
Simultaneous graph drawing: layout algorithms and visualization schemes.
Small maximal independent sets and faster exact graph coloring.
Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including...
Spanning trees with leaves bounded by independence number.
Spanning trees with many or few colors in edge-colored graphs
Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.
Stable sets for -free graphs
The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for -free graphs in polynomial time, extending some known results.
Stacks, queues and tracks: layouts of graph subdivisions.
Star Coloring of Subcubic Graphs
A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.
Straight-line drawings of binary trees with linear area and arbitrary aspect ratio.
Subtree Matching by Pushdown Automata
Sur la réunion des arbres maximaux d'un graphe totalement préordonné. Note auto-critique
Un algorithme pour la recherche de la réunion des arbres maximaux (RAM) d'un graphe préordonné était proposé dans un article précédent (Math. Inf. Sci. hum. n°114, 1991, 35-40). Cet algorithme, qui était incorrect, est complété, justifié et illustré par un exemple dans cette note.