## 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},.,e_{r}) such that for every i = l,.,r-1, there are at most k vertices both incident to an edge that belongs to {e_{1},.,e _{i}} and to an edge that belongs to {e_{i+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 language | English (US) |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Editors | Rod Downey, Michael Fellows, Frank Dehne |

Publisher | Springer Verlag |

Pages | 37-48 |

Number of pages | 12 |

ISBN (Print) | 9783540230717 |

DOIs | |

State | Published - 2004 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 3162 |

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.