Optimal register allocation for SSA-form programs in polynomial time

This paper gives a constructive proof that the register allocation problem for a uniform register set is solvable in polynomial time for SSA-form programs.     

Tutte type theorems for graphs having a perfect internal matching

Splitters are introduced to capture the meaning of barriers in graphs having a perfect internal matching. The factor-critical property is extended in a natural way to accommodate such graphs, and a characterization of factor-critical graphs is given in the new context. Two Tutte type theorems are presented for open graphs with perfect internal matchings, one on maximal splitters, and the other on maximal inaccessible splitters.     

On packing shortest cycles in graphs

We study the problems to find a maximum packing of shortest edge-disjoint cycles in a graph of given girth g (g-ESCP) and its vertex-disjoint analogue g-VSCP. In the case g=3, Caprara and Rizzi (2001) have shown that g-ESCP can be solved in polynomial time for graphs with maximum degree 4, but is APX-hard for graphs with maximum degree 5, while g-VSCP can be solved in polynomial time for graphs with maximum degree 3, but is APX-hard for graphs with maximum degree 4. For g∈{4,5}, we show that both problems allow polynomial time algorithms for instances with maximum degree 3, but are APX-hard for instances with maximum degree 4. For each g?6, both problems are APX-hard already for graphs with maximum degree 3.     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

A note on t-complementing permutations for graphs

In this note we present a necessary and sufficient condition for a permutation to be t-complementing which is a natural generalization of the well-known result concerning self-complementing permutations.     

An efficient distributed algorithm for maximum matching in general graphs

We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n ^5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570.     

Partition-distance: A problem and class of perfect graphs arising in clustering

Partitioning of a set of elements into disjoint clusters is a fundamental problem that arises in many applications. Different methods produce different partitions, so it is useful to have a measure of the similarity, or distance, between two or more partitions. In this paper we examine one distance measure used in a clustering application in computational genetics. We show how to efficiently compute the distance, and how this defines a new class of perfect graphs.     

Some optimization problems on weak-bisplit graphs

A new decomposition scheme for bipartite graphs namely canonical decomposition was introduced by Fouquet et al. [Internat. J. Found. Comput. Sci. 10 (1999) 513-533]. The so-called weak-bisplit graphs are totally decomposable following this decomposition. We present here some optimization problems for general bipartite graphs which have efficient solutions when dealing with weak-bisplit graphs.     

A linear algorithm for the all-bidirectional-edges problem on planar graphs

The all-bidirectional-edges problem is to find an edge-labeling of an undirected networkG=(V, E), with a source and a sink, such that an edgee=uv inE is labeled u, v or u, u (or both) depending on the existence of a (simple) path from the source to the sink traversinge, that visits the verticesu andv in the orderu, v orv, u respectively. The best-known algorithm for this problem requiresO(¦V¦·¦E¦) time [5]. We show that the problem is solvable optimally on a planar graph.     

A characterization of complete bipartite RAC graphs

A Right Angle Crossing drawing (RAC drawing for short) of a graph is such that edges can only cross at an angle of . In this paper we provide a characterization of the complete bipartite graphs that admit a straight-line RAC drawing.     

A linear time recognition algorithm for proper interval graphs

We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian cycle of G.     

Cluster editing problem for points on the real line: A polynomial time algorithm

In this paper we consider the cluster editing problem for a special type of graphs, where the vertices represent points on the real line and there is an edge between each two vertices for which the distance between their corresponding points on the line is less than a given constant. We give a polynomial time cluster editing algorithm for this class of graphs.     

On mimicking networks representing minimum terminal cuts

Given a capacitated undirected graph G=(V,E)$G=(V,E)$ with a set of terminals K⊂V$K\subset V$, a mimicking network   is a smaller graph H=(_VH,_EH)$H=(V_H,E_H)$ which contains the set of terminals K   and for every bipartition [U,K−U]$[U,K-U]$ of the terminals, the cost of the minimum cut separating U   from K−U$K-U$ in G is exactly equal to the cost of the minimum cut separating U   from K−U$K-U$ in H.     

A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs

An edge ranking of a graph G is a labeling r of its edges with positive integers such that every path between two different edges eu, ev with the same rank r(eu)=r(ev) contains an intermediate edge ew with rank r(ew)>r(eu). An edge ranking of G is minimum if the largest rank k assigned is the smallest among all rankings of G. The edge ranking problem is to find a minimum edge ranking of given graph G. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of trees. In this paper, we first show, on a general graph G, a relation between a minimum edge ranking of G and its minimal cuts, which ensures that we can obtain a polynomial time algorithm for obtaining minimum edge ranking of a given graph G if minimal cuts for each subgraph of G can be found in polynomial time and the number of those is polynomial. Based on this relation, we develop a polynomial time algorithm for finding a minimum edge ranking on a 2-connected outerplanar graph.