\(k\)-chordal graphs: from cops and robber to compact routing via treewidth
From MaRDI portal
Publication:494802
DOI10.1007/s00453-014-9871-yzbMath1328.68152OpenAlexW1967614940WikidataQ62046034 ScholiaQ62046034MaRDI QIDQ494802
Publication date: 2 September 2015
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-014-9871-y
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)
Related Items (6)
Treelength of series-parallel graphs ⋮ Tree-chromatic number ⋮ Pathlength of outerplanar graphs ⋮ Cops and robber on subclasses of \(P_5\)-free graphs ⋮ Study of a combinatorial game in graphs through linear programming ⋮ Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Distributed computing of efficient routing schemes in generalized chordal graphs
- Hyperbolicity and chordality of a graph
- Monadic second-order evaluations on tree-decomposable graphs
- A game of cops and robbers
- Graph minors. III. Planar tree-width
- On the complexity of computing treelength
- A short note about pursuit games played on a graph with a given genus
- Cops and robbers in graphs with large girth and Cayley graphs
- On a pursuit game played on graphs for which a minor is excluded
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth for graphs with small chordality
- Vertex-to-vertex pursuit in a graph
- Tree-decompositions with bags of small diameter
- Additive spanners and distance and routing labeling schemes for hyperbolic graphs
- Tandem-win graphs
- On Meyniel's conjecture of the cop number
- Cop and Robber Games When the Robber Can Hide and Ride
- k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth
- A Bound for the Cops and Robbers Problem
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Compact Routing in Power-Law Graphs
- Complexity of Finding Embeddings in a k-Tree
- Treewidth of Circular-Arc Graphs
- 1-Hyperbolic Graphs
- The Pathwidth and Treewidth of Cographs
- Treewidth of Chordal Bipartite Graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Compact name-independent routing with minimum stretch
- Object location using path separators
- Optimal-stretch name-independent compact routing in doubling metrics
- Collective dynamics of ‘small-world’ networks
- Distributed Computing
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: \(k\)-chordal graphs: from cops and robber to compact routing via treewidth
