The complexity of two graph orientation problems
From MaRDI portal
Publication:412352
DOI10.1016/J.DAM.2011.10.036zbMATH Open1236.05113arXiv1004.2478OpenAlexW2112534214MaRDI QIDQ412352FDOQ412352
Steven D. Noble, Nicole Eggemann
Publication date: 4 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Abstract: We consider two orientation problems in a graph, namely the minimization of the sum of all the shortest path lengths and the minimization of the diameter. We show that it is NP-complete to decide whether a graph has an orientation such that the sum of all the shortest paths lengths is at most an integer specified in the input. The proof is a short reduction from a result of Chv'atal and Thomassen showing that it is NP-complete to decide whether a graph can be oriented so that its diameter is at most 2. In contrast, for each positive integer k, we describe a linear-time algorithm that decides for a planar graph G whether there is an orientation for which the diameter is at most k. We also extend this result from planar graphs to any minor-closed family not containing all apex graphs.
Full work available at URL: https://arxiv.org/abs/1004.2478
Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Paths and cycles (05C38) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- On orientations and shortest paths
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Easy problems for tree-decomposable graphs
- Digraphs
- Quickly excluding a planar graph
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Graph minor theory
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- Graph minors. III. Planar tree-width
- Distances in orientations of graphs
- Diameter and treewidth in minor-closed graph families
- The monadic second-order logic of graphs. VIII: Orientations
- Optimal orientations of graphs and digraphs: A survey
- Complexity of approximating the oriented diameter of chordal graphs
- Linearity of grid minors in treewidth with applications through bidimensionality
- Diameter and treewidth in minor-closed graph families, revisited
- Minimizing the oriented diameter of a planar graph
- Bidimensional Parameters and Local Treewidth
- Separating systems and oriented graphs of diameter two
Cited In (7)
- On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
- Orientable burning number of graphs
- Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
- Complexity dichotomy for oriented homomorphism of planar graphs with large girth
- The complexity of deciding whether a graph admits an orientation with fixed weak diameter
- On the Query Complexity of Testing Orientations for Being Eulerian
- The complexity of the proper orientation number
Recommendations
- Title not available (Why is that?) 👍 👎
- Approximation Algorithms and Hardness Results for Shortest Path Based Graph Orientations 👍 👎
- The complexity of 2-vertex-connected orientation in mixed graphs 👍 👎
- The complexity of deciding whether a graph admits an orientation with fixed weak diameter 👍 👎
- On the orientation of graphs and hypergraphs 👍 👎
- NP-completeness of st-orientations for plane graphs 👍 👎
- Complexity dichotomy for oriented homomorphism of planar graphs with large girth 👍 👎
- NP-Completeness of st-Orientations for Plane Graphs 👍 👎
- Parameterized st-Orientations of Graphs: Algorithms and Experiments 👍 👎
- The orientation number of two complete graphs with linkages 👍 👎
This page was built for publication: The complexity of two graph orientation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412352)
