Computing the vertex separation of unicyclic graphs

DOI10.1016/j.ic.2004.03.005zbMath1069.68077OpenAlexW1973873776MaRDI QIDQ596295

Sumit K. Garg

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

zbMATH Keywords

AlgorithmsTreesLayout extensibilityLinear layoutsPathwidthSearch numberUnicyclic graphsVertex separation

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Combining intensification and diversification strategies in VNS. An application to the vertex separation problem ⋮ Variable neighborhood search for the vertex separation problem ⋮ Edge Search Number of Cographs in Linear Time ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Approximate search strategies for weighted trees ⋮ Edge search number of cographs ⋮ Pathwidth of Circular-Arc Graphs ⋮ An annotated bibliography on guaranteed graph searching ⋮ A 3-approximation for the pathwidth of Halin graphs ⋮ Non-deterministic graph searching in trees

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