k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth

DOI10.1007/978-3-642-31585-5_54zbMath1318.68127OpenAlexW1726008105MaRDI QIDQ3167048

Nicolas Nisse, Adrian Kosowski, Bi Li, Karol Suchan

Publication date: 1 November 2012

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-31585-5_54

zbMATH Keywords

treewidthchordalitycompact routingcops and robber games

Mathematics Subject Classification ID

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 (5)

Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond ⋮ Cops and Robbers on Dynamic Graphs: Offline and Online Case ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Tree decompositions and social graphs ⋮ In absence of long chordless cycles, large tree-width becomes a local phenomenon

This page was built for publication: k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth