Connected Treewidth and Connected Graph Searching

DOI10.1007/11682462_45zbMath1145.68473MaRDI 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

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

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