On the Vertex Separation of Cactus Graphs

Authors: Markov, Minko
Issue Date: 2007
Citation: Serdica Journal of Computing, Vol. 1, No 1, (2007), 45p-72p Copy to clipboard
ISSN: 1312-6555
URI: http://hdl.handle.net/10525/333 Copy to clipboard
Abstract: This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a main theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.
Language: en
Publisher: Institute of Mathematics and Informatics, Bulgarian Academy of SciencesSubject: Algorithmic Graph TheoryComputational ComplexityVertex SeparationLinear LayoutLayout ExtensibilityLayout StretchabilityCactus Graph
Type: Article