Back to Search
Start Over
Non-Deterministic Graph Searching: From Pathwidth to Treewidth
- Source :
- Algorithmica, Algorithmica, 2009, 53 (3), pp.358-373. ⟨10.1007/s00453-007-9041-6⟩, Algorithmica, Springer Verlag, 2009, 53 (3), pp.358-373. ⟨10.1007/s00453-007-9041-6⟩, Mathematical Foundations of Computer Science 2005 ISBN: 9783540287025, MFCS, Springer, LNCS 3618, Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2005, Poland. pp.364-375, ⟨10.1007/11549345_32⟩, Scopus-Elsevier
- Publication Year :
- 2009
- Publisher :
- HAL CCSD, 2009.
-
Abstract
- International audience; We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.
- Subjects :
- General Computer Science
Treewidth
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Pathwidth
02 engineering and technology
0102 computer and information sciences
Computer Science::Computational Complexity
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Tree-depth
01 natural sciences
Combinatorics
Partial k-tree
0202 electrical engineering, electronic engineering, information engineering
0101 mathematics
Mathematics
Graph searching
Discrete mathematics
Applied Mathematics
010102 general mathematics
Tree decomposition
Computer Science Applications
Nondeterministic algorithm
Graph bandwidth
010201 computation theory & mathematics
Graph (abstract data type)
020201 artificial intelligence & image processing
Subjects
Details
- Language :
- English
- ISBN :
- 978-3-540-28702-5
- ISSN :
- 01784617 and 14320541
- ISBNs :
- 9783540287025
- Database :
- OpenAIRE
- Journal :
- Algorithmica, Algorithmica, 2009, 53 (3), pp.358-373. ⟨10.1007/s00453-007-9041-6⟩, Algorithmica, Springer Verlag, 2009, 53 (3), pp.358-373. ⟨10.1007/s00453-007-9041-6⟩, Mathematical Foundations of Computer Science 2005 ISBN: 9783540287025, MFCS, Springer, LNCS 3618, Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2005, Poland. pp.364-375, ⟨10.1007/11549345_32⟩, Scopus-Elsevier
- Accession number :
- edsair.doi.dedup.....e032b0079169acafb493d974b289c045