Computing the vertex separation of unicyclic graphs

DOI10.1016/J.IC.2004.03.005zbMATH Open1069.68077OpenAlexW1973873776MaRDI QIDQ596295FDOQ596295

Authors 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

AlgorithmsLayout extensibilityLinear layoutsPathwidthSearch numberTreesUnicyclic graphsVertex separation

Mathematics Subject Classification ID

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

Recommendations

• Searching Cycle-Disjoint Graphs
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• scientific article; zbMATH DE number 1670677
• The vertex separation number of a graph equals its path-width
• Publication:3197863

Cites Work

• scientific article; zbMATH DE number 1670677 (Why is no real title available?)
• scientific article; zbMATH DE number 1222842 (Why is no real title available?)
• Approximating the pathwidth of outerplanar graphs
• Approximation of pathwidth of outerplanar graphs
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Interval graphs and searching
• Min Cut is NP-complete for edge weighted trees
• Recontamination does not help to search a graph
• Searching and pebbling
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width

Cited In (14)

• 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
• On the vertex separation of cactus 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
• Searching Cycle-Disjoint Graphs
• 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)