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

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

Fedor V. Fomin, Rodica Mihai, Pinar Heggernes

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

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

Related Items

Edge Search Number of Cographs in Linear Time ⋮ Mixed Search Number of Permutation Graphs ⋮ The complexity of zero-visibility cops and robber ⋮ Edge search number of cographs ⋮ An annotated bibliography on guaranteed graph searching

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