Algorithmic Graph Theory Computational Complexity Vertex Separation Linear Layout Layout Extensibility Layout Stretchability Cactus Graph
Issue Date:
2007
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 1, No 1, (2007), 45p-72p
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.
