Algorithms and obstructions for linear-width and related search parameters
From MaRDI portal
Publication:1582084
DOI10.1016/S0166-218X(00)00175-XzbMath0958.05124OpenAlexW1971764330MaRDI QIDQ1582084
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
Graph minors (05C83) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Contraction obstructions for connected graph searching, Graph Minors and Parameterized Algorithm Design, Sparse obstructions for minor-covering parameters, Outerplanar obstructions for matroid pathwidth, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Outerplanar obstructions for a feedback vertex set, Forbidden graphs for tree-depth, Graph Searching in a Crime Wave, Mixed Search Number and Linear-Width of Interval and Split Graphs, On strict brambles, On the monotonicity of games generated by symmetric submodular functions., Characterizing graphs of small carving-width, An annotated bibliography on guaranteed graph searching, Forbidden minors for graphs with no first obstruction to parametric Feynman integration, Digraph searching, directed vertex separation and directed pathwidth, A 3-approximation for the pathwidth of Halin graphs, Four-searchable biconnected outerplanar graphs, A 3-approximation for the pathwidth of Halin graphs, Unnamed Item, Mixed search number and linear-width of interval and split graphs, Minor obstructions for apex-pseudoforests, Excluded vertex-minors for graphs of linear rank-width at most \(k\), Outerplanar Obstructions for the Feedback Vertex Set, Obstructions for Tree-depth, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Mixed searching and proper-path-width
- Forbidden minors characterization of partial 3-trees
- Interval graphs and searching
- Characterization of partial 3-trees in terms of three structures
- The vertex separation number of a graph equals its path-width
- On obstructions to small face covers in planar graphs
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- Parallel concepts in graph theory
- The vertex separation and search number of a graph
- Obstruction set isolation for the gate matrix layout problem
- On search, decision, and the efficiency of polynomial-time algorithms
- On interval routing schemes and treewidth
- Fugitive-search games on graphs and related parameters
- Searching and pebbling
- Graph minors. XIII: The disjoint paths problem
- A characterization of partial 3-trees
- Disjoint Paths—A Survey
- The complexity of searching a graph
- Nonconstructive tools for proving polynomial-time decidability
- Monotonicity in graph searching
- Graphs with Branchwidth at Most Three
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Parameterized and Exact Computation
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
