Computing small search numbers in linear time*

Hans L. Bodlaender, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsRod Downey, Michael Fellows, Frank Dehne
PublisherSpringer Verlag
Pages37-48
Number of pages12
ISBN (Print)9783540230717
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3162
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • Characteristics
  • Graph searching
  • Linear - Width
  • Pathwidth
  • Treewidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Computing small search numbers in linear time*'. Together they form a unique fingerprint.

Cite this