Connected Treewidth and Connected Graph Searching

DOI10.1007/11682462_45zbMath1145.68473OpenAlexW1874754796MaRDI QIDQ3525783

Nicolas Nisse, Pierre Fraigniaud

Publication date: 18 September 2008

Published in: LATIN 2006: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11682462_45

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (23)

On computational complexity of graph inference from counting ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ The cost of monotonicity in distributed graph searching ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ Approximating Pathwidth for Graphs of Small Treewidth ⋮ Connected search for a lazy robber ⋮ Combining restarts, nogoods and bag-connected decompositions for solving csps ⋮ An annotated bibliography on guaranteed graph searching ⋮ Distributed chasing of network intruders ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Connected graph searching ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Connected graph searching in chordal graphs ⋮ Bounding Connected Tree-Width ⋮ Network Decontamination with Temporal Immunity by Cellular Automata ⋮ Contiguous search problem in Sierpiński graphs ⋮ Connected searching of weighted trees ⋮ Monotony properties of connected visible graph searching ⋮ Graph searching with advice ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ Finding small-width connected path decompositions in polynomial time ⋮ Sweeping graphs with large clique number

This page was built for publication: Connected Treewidth and Connected Graph Searching