On the Vertex Separation of Cactus Graphs
DOI:
https://doi.org/10.55630/sjc.2007.1.45-72Keywords:
Algorithmic Graph Theory, Computational Complexity, Vertex Separation, Linear Layout, Layout Extensibility, Layout Stretchability, Cactus GraphAbstract
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.References
Bodlaender H. L., T. Kloks. Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs. J. Algorithms 21 (1996), No. 2, 358–402.
Ellis J., M. Markov. Computing the Vertex Separation of Unicyclic Graphs. Information and Computation 192 (2004), 123–161.
Ellis J. A., I. H. Sudborough, J. S. Turner. The Vertex Separation and Search Number of a Graph. Information and Computation 113, No 1 (1994), 50–79.
Gibbons A. Algorithmic Graph Theory. Cambridge University Press, 1985.
Kirousis L. M., C. H. Papadimitriou. Searching and pebbling. Theoretical Computer Science 47, No. 2 (1986), 205–218.
Markov M. A Fast Practical Algorithm for the Vertex Separation of Uncyclic Graps. Master’s thesis, University of Victoria, Dec. 2004.
Skodinis K. Computing optimal strategies for trees in linear time. Proceedings of the 8th Annual European Symposium on Algorithms, 2000, 403–414.
