The complexity of two graph orientation problems
From MaRDI portal
Publication:412352
DOI10.1016/j.dam.2011.10.036zbMath1236.05113arXiv1004.2478OpenAlexW2112534214MaRDI QIDQ412352
Steven D. Noble, Nicole Eggemann
Publication date: 4 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1004.2478
Paths and cycles (05C38) Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. III. Planar tree-width
- Separating systems and oriented graphs of diameter two
- Linearity of grid minors in treewidth with applications through bidimensionality
- On orientations and shortest paths
- Distances in orientations of graphs
- Quickly excluding a planar graph
- Diameter and treewidth in minor-closed graph families
- Diameter and treewidth in minor-closed graph families, revisited
- The monadic second-order logic of graphs. VIII: Orientations
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Optimal orientations of graphs and digraphs: A survey
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Minimizing the Oriented Diameter of a Planar Graph
- Easy problems for tree-decomposable 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
- Complexity of approximating the oriented diameter of chordal graphs
- Bidimensional Parameters and Local Treewidth
- Digraphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: The complexity of two graph orientation problems
