Please use this identifier to cite or link to this item: http://hdl.handle.net/10525/333

 Title: On the Vertex Separation of Cactus Graphs Authors: Markov, Minko Keywords: Algorithmic Graph TheoryComputational ComplexityVertex SeparationLinear LayoutLayout ExtensibilityLayout StretchabilityCactus 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. URI: http://hdl.handle.net/10525/333 ISSN: 1312-6555 Appears in Collections: Volume 1 Number 1

Files in This Item:

File Description SizeFormat