Computing the vertex separation of unicyclic graphs
From MaRDI portal
Publication:596295
DOI10.1016/j.ic.2004.03.005zbMath1069.68077MaRDI QIDQ596295
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
Algorithms; Trees; Layout extensibility; Linear layouts; Pathwidth; Search number; Unicyclic graphs; Vertex separation
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Edge Search Number of Cographs in Linear Time, Pathwidth is NP-Hard for Weighted Trees, A 3-approximation for the pathwidth of Halin graphs, Edge search number of cographs, An annotated bibliography on guaranteed graph searching, Approximate search strategies for weighted trees, Non-deterministic graph searching in trees, Pathwidth of Circular-Arc Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Approximating the pathwidth of outerplanar graphs
- Interval graphs and searching
- Min Cut is NP-complete for edge weighted trees
- The vertex separation number of a graph equals its path-width
- The vertex separation and search number of a graph
- Searching and pebbling
- Approximation of pathwidth of outerplanar graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Recontamination does not help to search a graph