Mixed search number and linear-width of interval and split graphs

DOI10.1002/net.20373zbMath1204.68145WikidataQ60488629 ScholiaQ60488629MaRDI QIDQ3057182

Fedor V. Fomin, Pinar Heggernes, Rodica Mihai

Publication date: 24 November 2010

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20373

zbMATH Keywords

graph searching; linear width; mixed search number

Mathematics Subject Classification ID

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

Related Items

Outerplanar obstructions for matroid pathwidth

Cites Work

• 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
• Graph searching on some subclasses of chordal graphs
• Algorithms and obstructions for linear-width and related search parameters
• Computing the branchwidth of interval 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