article · 2005
Nondeterministic Graph Searching: From Pathwidth to Treewidth
Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse
Cited by 0Abstract and details only
Abstract
Abstract. 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.
Cite this paper
Fomin, F. V., Fraigniaud, P., & Nisse, N. (2005). Nondeterministic Graph Searching: From Pathwidth to Treewidth.
Fomin, Fedor V., et al. “Nondeterministic Graph Searching: From Pathwidth to Treewidth.” 2005.
Fomin, Fedor V., Pierre Fraigniaud, and Nicolas Nisse. 2005. “Nondeterministic Graph Searching: From Pathwidth to Treewidth.”
Fomin, F.V., Fraigniaud, P. and Nisse, N. (2005) ‘Nondeterministic Graph Searching: From Pathwidth to Treewidth’.
@article{fomin2005nondeterministic,
title = {{Nondeterministic Graph Searching: From Pathwidth to Treewidth}},
author = {Fomin, Fedor V. and Fraigniaud, Pierre and Nisse, Nicolas},
year = {2005}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.