The vertex separation number of a graph equals its path-width

DOI10.1016/0020-0190(92)90234-MzbMath0764.68121OpenAlexW2052867211MaRDI QIDQ1198094

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90234-m

zbMATH Keywords

computational complexity path-width decision algorithms graph's vertex separation number tree obstructions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (84)

The structure of obstructions to treewidth and pathwidth ⋮ Refinements on an enumeration scheme for solving a pattern sequencing problem ⋮ Bounding the search number of graph products ⋮ A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY ⋮ Approximating the pathwidth of outerplanar graphs ⋮ On the monotonicity of process number ⋮ Computing directed pathwidth in \(O(1.89^n)\) time ⋮ Fixed-Parameter Tractability, A Prehistory, ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ Combining intensification and diversification strategies in VNS. An application to the vertex separation problem ⋮ Unnamed Item ⋮ Variable neighborhood search for the vertex separation problem ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Strong-mixed searching and pathwidth ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Computing the vertex separation of unicyclic graphs ⋮ Locating a robber with multiple probes ⋮ Approximate search strategies for weighted trees ⋮ Fugitive-search games on graphs and related parameters ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Order Reconfiguration under Width Constraints ⋮ On the complexity of the storyplan problem ⋮ Connected search for a lazy robber ⋮ On the treewidth of toroidal grids ⋮ Edge searching and fast searching with constraints ⋮ The complexity of zero-visibility cops and robber ⋮ The Treewidth and Pathwidth of Graph Unions ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ Connections between cutting-pattern sequencing, VLSI design, and flexible machines ⋮ A lower bound for the vertex boundary-width of complete \(k\)-ary trees ⋮ Unnamed Item ⋮ Interval degree and bandwidth of a graph ⋮ A distributed algorithm for computing the node search number in trees ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ Unnamed Item ⋮ Network decontamination under \(m\)-immunity ⋮ Parameterized algorithms for book embedding problems ⋮ Faster algorithms for finding and counting subgraphs ⋮ The theory of guaranteed search on graphs ⋮ Imbalance is fixed parameter tractable ⋮ Three-fast-searchable graphs ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ The Effect of Planarization on Width ⋮ Unnamed Item ⋮ An annotated bibliography on guaranteed graph searching ⋮ Computing the pathwidth of directed graphs with small vertex cover ⋮ Parameterized Algorithms for Book Embedding Problems ⋮ The complexity of minimum-length path decompositions ⋮ Node-searching problem on block graphs ⋮ PATH-WIDTH OF A GRAPH VS BRIDGE NUMBER OF A KNOT ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Neighbourhood-width of trees ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width ⋮ Lower bounds on the pathwidth of some grid-like graphs ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Fugitive-search games on graphs and related parameters ⋮ A note on exact algorithms for vertex ordering problems on graphs ⋮ Minimum dominating set of queens: a trivial programming exercise? ⋮ Finite graph automata for linear and boundary graph languages ⋮ The treewidth of proofs ⋮ CSP duality and trees of bounded pathwidth ⋮ Glauber dynamics on trees and hyperbolic graphs ⋮ Characterization of graphs and digraphs with small process numbers ⋮ Linear layouts measuring neighbourhoods in graphs ⋮ Linear ordering based MIP formulations for the vertex separation or pathwidth problem ⋮ The treewidth of line graphs ⋮ The Effect of Planarization on Width ⋮ On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering ⋮ Graph classes and the switch Markov chain for matchings ⋮ Better Algorithms and Bounds for Directed Maximum Leaf Problems ⋮ Derivation of algorithms for cutwidth and related graph layout parameters ⋮ Edge searching weighted graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ FPT is characterized by useful obstruction sets ⋮ A Polynomial Time Algorithm for Bounded Directed Pathwidth ⋮ Searching for a Visible, Lazy Fugitive ⋮ Edge and node searching problems on trees ⋮ On the hardness of palletizing bins using FIFO queues ⋮ Algorithms and obstructions for linear-width and related search parameters ⋮ Zero-visibility cops and robber and the pathwidth of a graph ⋮ Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth

Cites Work

This page was built for publication: The vertex separation number of a graph equals its path-width