# On the Vertex Separation of Cactus Graphs

Serdica Journal of Computing (2007)

- Volume: 1, Issue: 1, page 45-72
- ISSN: 1312-6555

## Access Full Article

top## Abstract

top## How to cite

topMarkov, 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 -

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.