International Journal of Foundations of Computer Science

Many practical problems (frequency assignement, register allocation, timetables) may be formulated as graph (vertex-)coloring problems, but finding solutions for them is difficult as long as they are treated in the most general case (where the graph is arbitrary), since vertex coloring has been proved to be NP-complete. The problem becomes much easier to solve if the graph resulting from the modelisation of the practical application belongs to some particular class of graphs, for which solutions to the problem are known. Meyniel graphs form such a class (a fast coloring algorithm can be found in [9]), for which an efficient recognizing algorithm is therefore needed.

A graph G=(V,E) is said to be a Meyniel graph if every odd cycle of G on at least five vertices contains at least two chords. Meyniel graphs generalize both i-triangulated and parity graphs, two well known classes of perfect graphs that will be present in our paper in Section 7.

In [2], Burlet and Fonlupt propose a characterization of Meyniel graphs which relies on the following property: the class of Meyniel graphs may be obtained from some basic Meyniel graphs using a binary operation called amalgam. Besides the theoretical interest of this result, a practical interest arises because of the polynomial recognition algorithm which can be obtained. Unfortunately, it is quite expensive to verify if a given graph is the amalgam of two graphs (therefore the complexity of the whole algorithm is in O(n⁷)), and this supports the idea that a new point of view is needed to find a more efficient algorithm.

Our approach of Meyniel graphs will be directed through the search of a general structure. Intuitively, a Meyniel graph either will be simple (i.e. with no hole or domino), or will have a skeleton around which the rest of the graph will be regularly organized. As suggested, the first type of Meyniel graphs is simple to identify. For the second type, a deeper analysis is necessary; it yields a characterization theorem, which is used to deduce the O(m²+mn) recognition algorithm.

Partition refinement techniques lead to simple and efficient algorithms for various applications: automaton minimization, string sorting … and also for algorithms on graphs. A generic algorithm that can be used for all these applications is presented and briefly discussed. Such an approach is interesting in an algorithmic tool kit perspective. New instances of the generic algorithm are presented: O(n+mlog n) very simple and practical algorithms for cographs recognition and for modular decomposition are designed. Although these algorithms are not linear, they are very easy to implement (as an instanciation of a generic procedure) and based on new ideas.

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k. However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that the k paths connecting r and any vertex v in the k trees are internally disjoint. In this paper we give a linear-time algorithm to find four independent spanning trees in a 4-connected planar graph.

We study the problem of adaptive polling in undirected general networks. Polling, also known as broadcast-confirm, consists a propagation round and a feedback round. In adaptive polling, a spanning tree of unknown topology is built dynamically during the propagation round, and feedback messages are free to choose their paths in order to adapt to traffic and fault situations. We study three adaptive polling algorithms and analyze their worst-case communication bit complexities in the propagation round. Then, we prove a lower bound on the worst-case communication bit complexity of Ω(e+nlog n) in the propagation round for all algorithms of the same kind as the three algorithms we study, where n is the number of nodes, and e the number of edges. We conclude that the cost introduced into the network due to the running of an adaptive polling algorithm is mild.

The problem of partitioning a graph such that the number of edges incident to vertices in different partitions is minimized, arises in many contexts. Some examples include its recursive application for minimizing fill-in in matrix factorizations and load-balancing for parallel algorithms. Spectral graph partitioning algorithms partition a graph using the eigenvector associated with the second smallest eigenvalue of a matrix called the graph Laplacian. The focus of this paper is the use graph theory to compute this eigenvector more quickly.