The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class AC ¹. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to UL∩coUL. As a consequence of our method we get that the isomorphism problem for oriented graphs is in NL. We also show that the problems are hard for L.     

The Longest Path Problem Is Polynomial on Cocomparability Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. As a generalization of the Hamiltonian path problem, it is NP-complete on general graphs and, in fact, on every class of graphs that the Hamiltonian path problem is NP-complete. Polynomial solutions for the longest path problem have recently been proposed for weighted trees, Ptolemaic graphs, bipartite permutation graphs, interval graphs, and some small classes of graphs. Although the Hamiltonian path problem on cocomparability graphs was proved to be polynomial almost two decades ago, the complexity status of the longest path problem on cocomparability graphs has remained open; actually, the complexity status of the problem has remained open even on the smaller class of permutation graphs. In this paper, we present a polynomial-time algorithm for solving the longest path problem on the class of cocomparability graphs. Our result resolves the open question for the complexity of the problem on such graphs, and since cocomparability graphs form a superclass of both interval and permutation graphs, extends the polynomial solution of the longest path problem on interval graphs and provides polynomial solution to the class of permutation graphs.     

An Isoperimetric Problem in Cayley Graphs

Let T be a minimal generating subset of a group G . Let Γ be the Cayley graph defined on G by . Let d ₂ be the minimal cardinality of the boundary of two points. We show that, for |S|>4 , every cutset with cardinality less than d ₂ must isolate a single vertex. Received April 1996, and in final form February 1999.     

The Steiner Problem in Graphs: Topological Methods of Solution

Algorithms for the Steiner problem and its generalizations on large graphs with a relatively small number of terminal vertices are designed by a two-level solution scheme: a network topology (i.e., a tree determining the adjacency of terminal vertices and branching points) is determined in the upper level and the optimal location for branching points with the topology found in the upper level is determined in the lower level.     

The Minimum Weight Dominating Set Problem for Permutation Graphs Is in NC

In this paper, we show that the problem of finding a minimum weight dominating set in a permutation graph, where a positive weight is assigned to each vertex, is in NC by presenting an O(log n) parallel algorithm with polynomially many processors on the CRCW model.     

The Longest Path Problem has a Polynomial Solution on Interval Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n ⁴) time, where n is the number of vertices of the input graph.     

低度图的点覆盖和独立集问题下界改进

给出了一种提高低度图点覆盖和独立集问题下界的精确算法．通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1．1033^n),参数化的3度图点覆盖问题的解决时间为O(kn 1．2174^k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1．1033^n)的解．以上3结果均打破原有最佳下界。     

On the Sum Coloring Problem on Interval Graphs

In this paper we study the following NP-complete problem: given an interval graph G = (V,E) , find a node p -coloring such that the cost is minimal, where denotes a partition of V whose subsets are ordered by nonincreasing cardinality. We present an O(m χ (G) + n log n) time ε -approximate algorithm (ε < 2) to solve the problem, where n , m , and χ #(G) are the number of nodes of the interval graph, its number of cliques, and its chromatic number, respectively. The algorithm is shown to solve the problem exactly on some classes of interval graphs, namely, the proper and the containment interval graphs, and the intersection graphs of sets of ``short' intervals. The problem of determining the minimum number of colors needed to achieve the minimum over all p -colorings of G is also addressed. Received February 1, 1996; revised August 22, 1997.     

On Approximation Properties of the Independent Set Problem for Low Degree Graphs

The subject of this paper is the Independent Set problem for bounded node degree graphs. It is shown that the problem remains MAX SNP -complete even when graphs are restricted to being of degree bounded by 3 or to being 3-regular. Some related problems are also shown to be MAX SNP -complete at the lowest possible degree bounds. We next study a better polynomial time approximation of the problem for degree 3 graphs. The performance ratio is improved from the previous best of 5/4 to arbitrarily close to 6/5 for degree 3 graphs and to 7/6 for cubic graphs. When combined with existing techniques this result also leads to approximation ratios, (B+3)/5+ε for the independent set problem and 2-5/(B+3)+ε for the vertex cover problem on graphs of degree B , improving previous bounds for relatively small odd B . Received March 1996, and in final form May 1998.     

A Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.     

Straight-Line Drawing Algorithms for Hierarchical Graphs and Clustered Graphs

Hierarchical graphs and clustered graphs are useful non-classical graph models for structured relational information. Hierarchical graphs are graphs with layering structures; clustered graphs are graphs with recursive clustering structures. Both have applications in CASE tools, software visualization and VLSI design. Drawing algorithms for hierarchical graphs have been well investigated. However, the problem of planar straight-line representation has not been solved completely. In this paper we answer the question: does every planar hierarchical graph admit a planar straight-line hierarchical drawing? We present an algorithm that constructs such drawings in linear time. Also, we answer a basic question for clustered graphs, that is, does every planar clustered graph admit a planar straight-line drawing with clusters drawn as convex polygons? We provide a method for such drawings based on our algorithm for hierarchical graphs.     

线框图形的计算机双色立体显示技术

系统地介绍了在计算机上采用双色法对线框图形进行了立体显示的原理和方法并编制了相应程序。此方法简单易行,能达到更好的视觉效果。     

The Method of Colored Graphs for Simplifying Expressions with Indices

Programming and Computer Software - Computer algebra is increasingly used in research and applied computations. An example is tensor computations or, in a wide sense, simplification of expressions...