On the Vertex Separation of Cactus Graphs

Markov, Minko. "On the Vertex Separation of Cactus Graphs." Serdica Journal of Computing 1.1 (2007): 45-72. <http://eudml.org/doc/11412>.

@article{Markov2007,
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 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.},
author = {Markov, Minko},
journal = {Serdica Journal of Computing},
keywords = {Algorithmic Graph Theory; Computational Complexity; Vertex Separation; Linear Layout; Layout Extensibility; Layout Stretchability; Cactus Graph; algorithmic graph theory; computational complexity; vertex separation; linear layout; layout extensibility; layout stretchability; cactus graph},
language = {eng},
number = {1},
pages = {45-72},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {On the Vertex Separation of Cactus Graphs},
url = {http://eudml.org/doc/11412},
volume = {1},
year = {2007},
}

TY - JOUR
AU - Markov, Minko
TI - On the Vertex Separation of Cactus Graphs
JO - Serdica Journal of Computing
PY - 2007
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 1
IS - 1
SP - 45
EP - 72
AB - 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 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.
LA - eng
KW - Algorithmic Graph Theory; Computational Complexity; Vertex Separation; Linear Layout; Layout Extensibility; Layout Stretchability; Cactus Graph; algorithmic graph theory; computational complexity; vertex separation; linear layout; layout extensibility; layout stretchability; cactus graph
UR - http://eudml.org/doc/11412
ER -