On the Vertex Separation of Cactus Graphs
Authors: Markov, Minko 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.Publisher:
Institute of Mathematics and Informatics, Bulgarian Academy of SciencesSubject: Algorithmic Graph TheoryComputational ComplexityVertex SeparationLinear LayoutLayout ExtensibilityLayout StretchabilityCactus Graph
Issue Date: 2007
Citation:
Serdica Journal of Computing, Vol. 1, No 1, (2007), 45p-72p URI:
http://hdl.handle.net/10525/333
ISSN: 1312-6555
Language: en
Type: Article