Search

Recently, D. Corneil found a simple 3-sweep lexicographic breadth first search (LexBFS) algorithm for the recognition of proper interval graphs. We point out how to modify Corneil's algorithm to make it a certifying algorithm, and then describe a similar certifying 3-sweep LexBFS algorithm for the recognition of proper interval bigraphs. It follows from an earlier paper that the class of proper interval bigraphs is equal to the better known class of bipartite permutation graphs, and so we have a certifying algorithm for that class as well. All our algorithms run in time O(m+n), including the certification phase. The certificates of representability (the intervals) can be authenticated in time O(m + n). The certificates of nonrepresentability (the forbidden subgraphs) can be authenticated in time O(n). [ABSTRACT FROM AUTHOR]

Splitting off two edges su, sv in a graph G means deleting su, sv and adding a new edge uv. Let G = (V + s, E) be k-edge-connected in V (k ≥ 2) and let d(s) be even. Lovász proved that the edges incident to s can be split off in pairs in a such a way that the resulting graph on vertex set V is k-edge-connected. In this paper we investigate the existence of such complete splitting sequences when the set of split edges has to meet additional requirements. We prove structural properties of the set of those pairs u, v of neighbors of s for which splitting off su, sv destroys k-edge-connectivity. This leads to a new method for solving problems of this type. By applying this method we obtain a short proof for a recent result of Nagamochi and Eades on planarity-preserving complete splitting sequences and prove the following new results: let G and H be two graphs on the same set V + s of vertices and suppose that their sets of edges incident to s coincide. Let G (H) be k-edge-connected (l-edge-connected, respectively) in V (k, l ≥ 2) and let d(s) be even. Then there exists a pair su, sv which can be split off in both graphs preserving k-edge-connectivity in G (l-edge-connectivity in H, respectively), provided d(s) ≥ 6. If k and l are both even, then such a pair always exists. By using these edge-splitting results and the polymatroid intersection theorem we give a polynomial algorithm for the problem of simultaneously augmenting the edge-connectivity of two graphs by adding a (common) set of new edges of (almost) minimum size. [ABSTRACT FROM AUTHOR]

There is a polynomial algorithm which finds a decomposition of any given 4-regular graph into two triangle-free 2-factors or shows that such a decomposition does not exist. [ABSTRACT FROM AUTHOR]

A graph is a split graph if its vertices can be partitioned into a clique and a stable set. A graph is a k-split graph if its vertices can be partitioned into k sets, each of which induces a split graph. We show that the strong perfect graph conjecture is true for 2-split graphs and we design a polynomial algorithm to recognize a perfect 2-split graph. [ABSTRACT FROM AUTHOR]

We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k ≥ 2, there is an O(V²) time algorithm that decides whether an undirected graph G = (V,E) contains a simple cycle of length 2k, and finds one if it does. (ii) There is an O(V²) time algorithm that finds a shortest even cycle in an undirected graph G = (V, E). [ABSTRACT FROM AUTHOR]