Geodesic
On the Vertex Separation of Cactus Graphs
Serdica Journal of Computing, Tome 1 (2007) no. 1, pp. 45-72

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

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.
Keywords: Algorithmic Graph Theory, Computational Complexity, Vertex Separation, Linear Layout, Layout Extensibility, Layout Stretchability, Cactus Graph 
@article{SJC_2007_1_1_a5,
     author = {Markov, Minko},
     title = {On the {Vertex} {Separation} of {Cactus} {Graphs}},
     journal = {Serdica Journal of Computing},
     pages = {45--72},
     publisher = {mathdoc},
     volume = {1},
     number = {1},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2007_1_1_a5/}
}
TY  - JOUR
AU  - Markov, Minko
TI  - On the Vertex Separation of Cactus Graphs
JO  - Serdica Journal of Computing
PY  - 2007
SP  - 45
EP  - 72
VL  - 1
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2007_1_1_a5/
LA  - en
ID  - SJC_2007_1_1_a5
ER  - 
%0 Journal Article
%A Markov, Minko
%T On the Vertex Separation of Cactus Graphs
%J Serdica Journal of Computing
%D 2007
%P 45-72
%V 1
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2007_1_1_a5/
%G en
%F SJC_2007_1_1_a5
Markov, Minko. On the Vertex Separation of Cactus Graphs. Serdica Journal of Computing, Tome 1 (2007) no. 1, pp. 45-72. http://geodesic.mathdoc.fr/item/SJC_2007_1_1_a5/