Algorithms and obstructions for linear-width and related search parameters

DOI10.1016/S0166-218X(00)00175-XzbMath0958.05124OpenAlexW1971764330MaRDI QIDQ1582084

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

zbMATH Keywords

graph algorithmgraph minorgraph searchingobstruction setlinear width

Mathematics Subject Classification ID

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