Computing the vertex separation of unicyclic graphs
DOI10.1016/J.IC.2004.03.005zbMATH Open1069.68077OpenAlexW1973873776MaRDI QIDQ596295FDOQ596295
Publication date: 10 August 2004
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2004.03.005
AlgorithmsLayout extensibilityLinear layoutsPathwidthSearch numberTreesUnicyclic graphsVertex separation
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Min Cut is NP-complete for edge weighted trees
- Searching and pebbling
- Recontamination does not help to search a graph
- The vertex separation number of a graph equals its path-width
- The vertex separation and search number of a graph
- Approximating the pathwidth of outerplanar graphs
- Interval graphs and searching
- Approximation of pathwidth of outerplanar graphs
Cited In (12)
- Pathwidth of Circular-Arc Graphs
- Non-deterministic graph searching in trees
- Edge Search Number of Cographs in Linear Time
- Edge search number of cographs
- A 3-approximation for the pathwidth of Halin graphs
- An annotated bibliography on guaranteed graph searching
- Approximate search strategies for weighted trees
- On some formulas in combinatorial computation of uni-trivalent graphs
- Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
- Variable neighborhood search for the vertex separation problem
- A method to calculate the number of spanning connected unicyclic(bicyclic) subgraphs in 2-separable networks
- Pathwidth is NP-Hard for Weighted Trees
This page was built for publication: Computing the vertex separation of unicyclic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q596295)
