BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2007 >
Volume 1 Number 1 >

Please use this identifier to cite or link to this item:

Title: On the Vertex Separation of Cactus Graphs
Authors: Markov, Minko
Keywords: 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.
ISSN: 1312-6555
Appears in Collections:Volume 1 Number 1

Files in This Item:

File Description SizeFormat
sjc014-vol1-num1-2007.pdf309.29 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License