Graph searching, elimination trees, and a generalization of bandwidth

DOI10.1007/S00453-004-1117-YMaRDI QIDQ1763148zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle

Publication date 21 February 2005

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-004-1117-y

zbMATH Keywords

BandwidthChordal graphElimination treeGraph searchingTree decomposition

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph searching, elimination trees, and a generalization of bandwidth.
• Lower bounds on treespan
• scientific article; zbMATH DE number 3858434
• Parameterized complexity of bandwidth on trees
• Laying out sparse graphs with provably minimum bandwidth

Cited in

(13)

• Edge searching weighted graphs
• Lower bounds on treespan
• Graph searching and a min-max theorem for tree-width
• On tradeoffs between width- and fill-like graph parameters
• Four-searchable biconnected outerplanar graphs
• On minimum cost edge searching
• The complexity of minimum-length path decompositions
• Graph searching, elimination trees, and a generalization of bandwidth.
• Edge-bandwidth of grids and tori
• Digraph measures: Kelly decompositions, games, and orderings
• An annotated bibliography on guaranteed graph searching
• Digraph searching, directed vertex separation and directed pathwidth
• Maximum vertex occupation time and inert fugitive: Recontamination does help

This page was built for publication: Graph searching, elimination trees, and a generalization of bandwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1763148)