The vertex separation number of a graph equals its path-width
From MaRDI portal
Recommendations
- The total vertex separation number of a graph
- The cutwidth of a graph and the vertex separation number of the line graph
- The total vertex separation number and profile of a graph
- On the path separation number of graphs
- The vertex detour number of a graph
- On the separation number of a graph
- Path Separability of Graphs
- The connected vertex detour number of a graph
- Equiparity path decomposition number of a graph
Cites work
- scientific article; zbMATH DE number 3590298 (Why is no real title available?)
- Black-white pebbles and graph separation
- Disjoint Paths—A Survey
- Graph minors. X: Obstructions to tree-decomposition
- Interval graphs and searching
- Nonconstructive advances in polynomial-time complexity
- Nonconstructive tools for proving polynomial-time decidability
- Recontamination does not help to search a graph
- Searching and pebbling
- The vertex separation and search number of a graph
Cited in
(only showing first 100 items - show all)- Pathwidth is NP-Hard for Weighted Trees
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- On the hardness of palletizing bins using FIFO queues
- Fugitive-search games on graphs and related parameters
- Minimum dominating set of queens: a trivial programming exercise?
- A note on exact algorithms for vertex ordering problems on graphs
- Parameterized algorithms for fixed-order book drawing with few crossings per edge
- Graph classes and the switch Markov chain for matchings
- The Treewidth and Pathwidth of Graph Unions
- On tradeoffs between width- and fill-like graph parameters
- A 3-approximation for the pathwidth of Halin graphs
- An annotated bibliography on guaranteed graph searching
- Locating a robber with multiple probes
- Searching for a Visible, Lazy Fugitive
- scientific article; zbMATH DE number 3854443 (Why is no real title available?)
- A partial k-arboretum of graphs with bounded treewidth
- The treewidth of line graphs
- Approximating the pathwidth of outerplanar graphs
- On the monotonicity of process number
- Computing directed pathwidth in O(1.89ⁿ) time
- Interval degree and bandwidth of a graph
- The mixed search game against an agile and visible fugitive is monotone
- A linear fixed parameter tractable algorithm for connected pathwidth
- A cops and robber game and the meeting time of synchronous directed walks
- Faster algorithms for finding and counting subgraphs
- The effect of planarization on width
- Approximate search strategies for weighted trees
- Connections between cutting-pattern sequencing, VLSI design, and flexible machines
- Edge searching weighted graphs
- Complexity framework for forbidden subgraphs. I: The framework
- Parameterized algorithms for book embedding problems
- Bounding the search number of graph products
- A lower bound for the vertex boundary-width of complete \(k\)-ary trees
- The complexity of zero-visibility cops and robber
- Edge and node searching problems on trees
- Graph homomorphism, monotone classes and bounded pathwidth
- Network decontamination under m-immunity
- Three-fast-searchable graphs
- The treewidth of proofs
- Strong-mixed searching and pathwidth
- The total vertex separation number of a graph
- The total vertex separation number and profile of a graph
- On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
- Digraph searching, directed vertex separation and directed pathwidth
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
- Edge-treewidth: algorithmic and combinatorial properties
- Polynomial threshold functions of bounded tree-width: some explainability and complexity aspects
- On the vertex separation of cactus graphs
- Parameterized algorithms for book embedding problems
- Order Reconfiguration under Width Constraints
- Fugitive-search games on graphs and related parameters
- On the monotonicity of games generated by symmetric submodular functions.
- On the treewidth of toroidal grids
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Variable neighborhood search for the vertex separation problem
- scientific article; zbMATH DE number 7651203 (Why is no real title available?)
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Path-width of a graph vs bridge number of a knot
- Linear layouts measuring neighbourhoods in graphs
- Algorithms and obstructions for linear-width and related search parameters
- Lower bounds on the pathwidth of some grid-like graphs
- On the complexity of the storyplan problem
- Computing the pathwidth of directed graphs with small vertex cover
- The effect of planarization on width
- Computing the vertex separation of unicyclic graphs
- Treewidth and pathwidth parameterized by the vertex cover number
- The theory of guaranteed search on graphs
- Node-searching problem on block graphs
- Linear ordering based MIP formulations for the vertex separation or pathwidth problem
- Derivation of algorithms for cutwidth and related graph layout parameters
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- A Polynomial Time Algorithm for Bounded Directed Pathwidth
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- The complexity of minimum-length path decompositions
- Graph parameters, universal obstructions, and WQO
- Glauber dynamics on trees and hyperbolic graphs
- Characterization of graphs and digraphs with small process numbers
- Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
- Better Algorithms and Bounds for Directed Maximum Leaf Problems
- The structure of obstructions to treewidth and pathwidth
- Refinements on an enumeration scheme for solving a pattern sequencing problem
- Neighbourhood-width of trees
- Complexity results for a cops and robber game on directed graphs
- A distributed algorithm for computing the node search number in trees
- Connected search for a lazy robber
- Imbalance is fixed parameter tractable
- CSP duality and trees of bounded pathwidth
- Randomly coloring graphs of logarithmically bounded pathwidth
- Finite graph automata for linear and boundary graph languages
- Graph searching on chordal graphs
- scientific article; zbMATH DE number 7471715 (Why is no real title available?)
- Zero-visibility cops and robber and the pathwidth of a graph
- Treewidth is NP-complete on cubic graphs
- Treewidth is NP-complete on cubic graphs
- Fixed-parameter tractability, a prehistory
- Constrained graph searching on trees
- Algorithms for solving problems on graphs of bounded pathwidth
- Edge searching and fast searching with constraints
- Fixed-parameter tractability of treewidth and pathwidth
- NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
This page was built for publication: The vertex separation number of a graph equals its path-width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198094)
