TY - CHAP
T1 - Computing small search numbers in linear time*
AU - Bodlaender, Hans L.
AU - Thilikos, Dimitrios M.
PY - 2004
Y1 - 2004
N2 - Let G = (V, E) be a graph. The linear - width of G is defined as the smallest integer k such that E can be arranged in a linear ordering (e 1,.,er) such that for every i = l,.,r-1, there are at most k vertices both incident to an edge that belongs to {e1,.,e i} and to an edge that belongs to {ei+1er}. For each fixed constant k, a linear time algorithm is given, that decides for any graph G = (V,E) whether the linear - width of G is at most k, and if so, finds the corresponding ordering of E. Linear - width has been proved to be related with the following graph searching parameters: mixed search number, node search number, and edge search number. A consequence of this is that we obtain for fixed k, linear time algorithms that check whether a given graph can be mixed, node, or edge searched with at most k searchers, and if so, output the corresponding search strategies.
AB - Let G = (V, E) be a graph. The linear - width of G is defined as the smallest integer k such that E can be arranged in a linear ordering (e 1,.,er) such that for every i = l,.,r-1, there are at most k vertices both incident to an edge that belongs to {e1,.,e i} and to an edge that belongs to {ei+1er}. For each fixed constant k, a linear time algorithm is given, that decides for any graph G = (V,E) whether the linear - width of G is at most k, and if so, finds the corresponding ordering of E. Linear - width has been proved to be related with the following graph searching parameters: mixed search number, node search number, and edge search number. A consequence of this is that we obtain for fixed k, linear time algorithms that check whether a given graph can be mixed, node, or edge searched with at most k searchers, and if so, output the corresponding search strategies.
KW - Characteristics
KW - Graph searching
KW - Linear - Width
KW - Pathwidth
KW - Treewidth
UR - http://www.scopus.com/inward/record.url?scp=35048890552&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=35048890552&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-28639-4_4
DO - 10.1007/978-3-540-28639-4_4
M3 - Chapter
AN - SCOPUS:35048890552
SN - 9783540230717
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 37
EP - 48
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Downey, Rod
A2 - Fellows, Michael
A2 - Dehne, Frank
PB - Springer Verlag
ER -