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

DOI10.1002/NET.20373MaRDI QIDQ3057182zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 searchinglinear widthmixed search number

Mathematics Subject Classification ID

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

Recommendations

• Parameterized and Exact Computation
• Fast-mixed searching on graphs
• Mixed Search Number of Permutation Graphs
• Algorithms and obstructions for linear-width and related search parameters
• Pathwidth and searching in parameterized threshold graphs

Cites work

• A 3-approximation for the pathwidth of Halin graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Algorithms and obstructions for linear-width and related search parameters
• Algorithms – ESA 2005
• Computing the Bandwidth of Interval Graphs
• Computing the branchwidth of interval graphs
• Graph searching on some subclasses of chordal graphs
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Interval graphs and searching
• Mixed searching and proper-path-width
• Monotonicity in graph searching
• On the interval completion of chordal graphs
• On the pathwidth of chordal graphs
• Optimal Linear Arrangement of Interval Graphs
• Recontamination does not help to search a graph
• Some generalizations of the problem on the search number of a graph
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The complexity of searching a graph

Cited in

(5)

• Pathwidth and searching in parameterized threshold graphs
• Outerplanar obstructions for matroid pathwidth
• Exclusive graph searching
• Parameterized and Exact Computation
• Exclusive graph searching vs. pathwidth

This page was built for publication: Mixed search number and linear-width of interval and split graphs

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