In this paper, we establish that any interval graph (resp. circular-arc graph) with n vertices admits a partition into at most inverted right perpendicularlog(3) ninverted left perpendicular (resp. inverted right perp...
详细信息
In this paper, we establish that any interval graph (resp. circular-arc graph) with n vertices admits a partition into at most inverted right perpendicularlog(3) ninverted left perpendicular (resp. inverted right perpendicularlog(3) ninverted left perpendicular + 1) proper interval subgraphs, for n> 1. The proof is constructive and provides an efficient algorithm to compute such a partition. On the other hand, this bound is shown to be asymptotically sharp for an infinite family of interval graphs. In addition, some results are derived for related problems. (C) 2010 Wiley Periodicals, Inc. J graph Theory 68: 38-54, 2011
In this paper, we establish a novel balanced separator theorem for Unit Disk graphs (UDGs), which mimics the well-known Lipton and Tarjan's planar balanced shortest paths separator theorem. We prove that, in any n...
详细信息
In this paper, we establish a novel balanced separator theorem for Unit Disk graphs (UDGs), which mimics the well-known Lipton and Tarjan's planar balanced shortest paths separator theorem. We prove that, in any n-vertex UDG G, one can find two hop-shortest paths P (s, x) and P (s, y) such that the removal of the 3-hop-neighborhood of these paths (i.e., NG3 [P (s, x) ∪ P (s, y)]) from G leaves no connected component with more than 2 / 3 n vertices. This new balanced shortest-paths-3- hop-neighborhood separator theorem allows us to build, for any n-vertex UDG G, a system T (G) of at most 2 logfrac(3, 2) n + 2 spanning trees of G such that, for any two vertices x and y of G, there exists a tree T in T (G) with dT (x, y) ≤ 3 ṡ dG (x, y) + 12. That is, the distances in any UDG can be approximately represented by the distances in at most 2 logfrac(3, 2) n + 2 of its spanning trees. Using these results, we propose a new compact and low delay routing labeling scheme for UDGs.
graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide...
详细信息
graph decompositions such as decomposition by clique separators and modular decomposition are of crucial importance for designing efficient graph algorithms. Clique separators in graphs were used by Tarjan as a divide-and-conquer approach for solving various problems such as the Maximum Weight Stable Set (MWS) problem, Colouring and Minimum Fill-in. The basic tool is a decomposition tree of the graph whose leaves have no clique separator (so-called atoms), and the problem can be solved efficiently on the graph if it is efficiently solvable on its atoms. We give new examples where the clique separator decomposition works well for the MWS problem;our results improve and extend various recently published results. In particular, we describe the atom structure for some new classes of graphs whose atoms are P-5-free (the P-5 is the induced path with five vertices) and obtain new polynomial time results for the MWS problem. The complexity of this problem on the class of P5-free graphs is still unknown. (c) 2006 Elsevier B.V. All rights reserved.
We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the grap...
详细信息
We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by gamma-proportion. We show that for multiple voting location, Condorcet and Simpson decision problems are Sigma(p)(2)-complete, and investigate the approximability of the Simpson and the Simpson score optimization problem. Further we contribute a result towards lower bounds on the complexity of the single voting location problem. On the positive side we develop algorithms for the optimization problems on tree networks which are substantially faster than the existing algorithms for general graphs. Finally we suggest a generalization of the indifference notion to threshold functions. (c) 2006 Elsevier B.V. All rights reserved.
The Maximum Weight Stable Set (MWS) Problem is one of the fundamental problems on graphs. It is well-known to be NP-complete for triangle-free graphs, and Mosca has shown that it is solvable in polynomial time when re...
详细信息
The Maximum Weight Stable Set (MWS) Problem is one of the fundamental problems on graphs. It is well-known to be NP-complete for triangle-free graphs, and Mosca has shown that it is solvable in polynomial time when restricted to P-6-and triangle-free graphs. We give a complete structure analysis of (nonbipartite) P-6-and triangle-free graphs which are prime in the sense of modular decomposition. It turns out that the structure of these graphs is simple implying bounded clique-width and thus, efficientalgorithms exist for all problems expressible in terms of Monadic Second Order Logic with quantification only over vertex predicates. The problems Vertex Cover, MWS, Maximum Clique, Minimum Dominating Set, Steiner Tree, and Maximum Induced Matching are among them. Our results improve the previous one on the MWS problem by Mosca with respect to structure and time bound but also extends a previous result by Fouquet, Giakoumakis, and Vanherpe which have shown that bipartite P-6-free graphs have bounded clique-width. Moreover, it covers a result by Randerath, Schiermeyer, and Tewes on polynomial time 3-colorability of P-6-and triangle-free graphs.
Modular decomposition of graphs is a powerful tool for designing efficientalgorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time...
详细信息
Modular decomposition of graphs is a powerful tool for designing efficientalgorithms for problems on graphs such as Maximum Weight Stable Set (MWS) and Maximum Weight Clique. Using this tool we obtain O(n (.) m) time algorithms for MWS on chair- and xbull-free graphs which considerably extend an earlier result on bull- and chair-free graphs by De Simone and Sassano (the chair is the graph with vertices a, b, c, d, e and edges ab, be, cd, be, and the xbull is the graph with vertices a, b, c, d, e, f and edges ab, be, cd, de, bf, cf). Moreover, our algorithm is robust in the sense that we do not have to check in advance whether the input graphs are indeed chair- and xbull-free. (C) 2003 Elsevier B.V. All rights reserved.
A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices is at most t times their distance in G. The TREE t-SPANNER problem asks whether a graph admits a tree ...
详细信息
A tree t-spanner T in a graph G is a spanning tree of G such that the distance in T between every pair of vertices 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 substantially strengthen the hardness result of Cai and Comeil (SIAM J. Discrete Math. 8 (1995) 359-387) by showing that, for any t greater than or equal to 4, TREE t-SPANNER is NP-complete even on chordal graphs of diameter at most t + 1 (if t is even), respectively, at most t + 2 (if t is odd). Then we point out that every chordal graph of diameter at most t - 1 (respectively, t - 2) admits a tree t-spanner whenever t greater than or equal to 2 is even (respectively, t greater than or equal to 3 is odd), and such a tree spanner can be constructed in linear time. The complexity status of TREE 3-SPANNER still remains open for chordal graphs, even on the subclass of undirected path graphs that are strongly chordal as well. For other important subclasses of chordal graphs, such as very strongly chordal graphs (containing all interval graphs), I-split graphs (containing all split graphs) and chordal graphs of diameter at most 2, we are able to decide TREE 3-SPANNER efficiently. (C) 2003 Elsevier B.V. All rights reserved.
暂无评论