Mixed Search Number and Linear-Width of Interval and Split Graphs

DOI10.1007/978-3-540-74839-7_29zbMath1141.68526MaRDI QIDQ3508577

Fedor V. Fomin, Pinar Heggernes, Rodica Mihai

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_29

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Edge Search Number of Cographs in Linear Time, Edge search number of cographs, An annotated bibliography on guaranteed graph searching, Mixed Search Number of Permutation Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixed searching and proper-path-width
• Interval graphs and searching
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the pathwidth of chordal graphs
• Some generalizations of the problem on the search number of a graph
• The theory of search games and rendezvous.
• Graph searching on some subclasses of chordal graphs
• Algorithms and obstructions for linear-width and related search parameters
• Computing the branchwidth of interval graphs
• Algorithmic graph theory and perfect graphs
• On the interval completion of chordal graphs
• Computing the Bandwidth of Interval Graphs
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• Algorithms – ESA 2005
• A Characterization of Comparability Graphs and of Interval Graphs
• Optimal Linear Arrangement of Interval Graphs
• A 3-approximation for the pathwidth of Halin graphs