A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite ...
详细信息
A graph is polar if its vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite, cobipartite, and split graphs. The problem of recognizing polar graphs is NP-complete in general. However, it has been shown to be polynomial for several classes of graphs, including cographs and chordal graphs. In this paper, we study the problem of recognizing graphs whose line graphs are polar. It turns out that the core part of this problem lies in determining whether the edge set of a graph admits a partition (A, B) so that A induces a P(3)-free subgraph (i.e., a matching) and B induces a P(4)-free subgraph. We give a structural characterization of such graphs. The characterization enables us to devise an O(n) timealgorithm to solve the stated recognition problem.
A graph is polar if the vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite ...
详细信息
A graph is polar if the vertex set can be partitioned into A and B in such a way that A induces a complete multipartite graph and B induces a disjoint union of cliques (i.e., the complement of a complete multipartite graph). Polar graphs naturally generalize several classes of graphs such as bipartite graphs, cobipartite graphs and split graphs. Recognizing polar graphs is an NP-complete problem in general, and thus it is of interest to restrict the problem to special classes of graphs. Cographs and chordal graphs are among those whose polarity can be recognized in polynomial time. The line-graphs of bipartite graphs are another class of graphs whose polarity has been characterized recently in terms of forbidden subgraphs, but no polynomial timealgorithm is given. In this paper, we present an O(n) algorithm which decides whether the line-graph of an input bipartite graph is polar and constructs a polar partition when one exists. (C) 2010 Elsevier B.V. All rights reserved.
A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was intro...
详细信息
A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos motivated by the search for underlying phylogenetic trees. Their results imply a O(n(3)) timerecognitionalgorithm for 3-leaf powers. Later, Dom, Guo, Huffner, and Niederineier characterized 3-leaf powers as the (bull. dart, gem)-free chordal graphs. We show that a connected graph is a 3-leaf power if and only if it results from substituting cliques into the vertices of a tree. This characterization is much simpler than the previous characterizations via critical cliques and forbidden induced subgraphs and also leads to lineartimerecognition of these graphs. (c) 2006 Elsevier B.V. All rights reserved.
We present a linear-timealgorithm for recognizing digitized circular arcs, by a reduction to linear programming in fixed dimensions. This generalizes the known results for both digital line segments and complete circ...
详细信息
We present a linear-timealgorithm for recognizing digitized circular arcs, by a reduction to linear programming in fixed dimensions. This generalizes the known results for both digital line segments and complete circles. Moreover, our idea is flexible enough to admit further extensions, such as recognizing disconnected subsets of digital circles and elliptical arcs.
暂无评论