Algorithms and obstructions for linear-width and related search parameters
From MaRDI portal
DOI10.1016/S0166-218X(00)00175-XzbMATH Open0958.05124OpenAlexW1971764330MaRDI QIDQ1582084FDOQ1582084
Authors: Dimitrios M. Thilikos 
Publication date: 27 February 2001
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00175-x
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph minors (05C83)
Cites Work
- Title not available (Why is that?)
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Searching and pebbling
- Graph minors. XIII: The disjoint paths problem
- Nonconstructive tools for proving polynomial-time decidability
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parallel concepts in graph theory
- Title not available (Why is that?)
- The complexity of searching a graph
- The vertex separation number of a graph equals its path-width
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- The vertex separation and search number of a graph
- Obstruction set isolation for the gate matrix layout problem
- Fugitive-search games on graphs and related parameters
- Monotonicity in graph searching
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Interval graphs and searching
- On search, decision, and the efficiency of polynomial-time algorithms
- Title not available (Why is that?)
- A characterization of partial 3-trees
- Forbidden minors characterization of partial 3-trees
- Title not available (Why is that?)
- On obstructions to small face covers in planar graphs
- Mixed searching and proper-path-width
- Title not available (Why is that?)
- Characterization of partial 3-trees in terms of three structures
- Disjoint Paths—A Survey
- Title not available (Why is that?)
- Graphs with Branchwidth at Most Three
- Monotonicity and inert fugitive search games
- On interval routing schemes and treewidth
- Title not available (Why is that?)
Cited In (28)
- Outerplanar obstructions for matroid pathwidth
- Outerplanar obstructions for a feedback vertex set
- Title not available (Why is that?)
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- A 3-approximation for the pathwidth of Halin graphs
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- Graph minors and parameterized algorithm design
- An annotated bibliography on guaranteed graph searching
- Four-searchable biconnected outerplanar graphs
- Contraction obstructions for connected graph searching
- Graph Searching in a Crime Wave
- A 3-approximation for the pathwidth of Halin graphs
- Digraph searching, directed vertex separation and directed pathwidth
- Characterizing graphs of small carving-width
- Minor obstructions for apex-pseudoforests
- On the monotonicity of games generated by symmetric submodular functions.
- Mixed search number and linear-width of interval and split graphs
- Obstructions for tree-depth
- Outerplanar obstructions for the feedback vertex set
- Forbidden graphs for tree-depth
- Sparse obstructions for minor-covering parameters
- Forbidden minors for graphs with no first obstruction to parametric Feynman integration
- A linear-time parameterized algorithm for computing the width of a DAG
- Outerplanar obstructions for matroid pathwidth
- On strict brambles
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Parameterized and Exact Computation
- Excluded vertex-minors for graphs of linear rank-width at most \(k\)
This page was built for publication: Algorithms and obstructions for linear-width and related search parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1582084)
