On the Vertex Separation of Cactus Graphs
| Data(s) |
16/09/2009
16/09/2009
2007
|
|---|---|
| Resumo |
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. |
| Identificador |
Serdica Journal of Computing, Vol. 1, No 1, (2007), 45p-72p 1312-6555 |
| Idioma(s) |
en_US |
| Publicador |
Institute of Mathematics and Informatics Bulgarian Academy of Sciences |
| Palavras-Chave | #Algorithmic Graph Theory #Computational Complexity #Vertex Separation #Linear Layout #Layout Extensibility #Layout Stretchability #Cactus Graph |
| Tipo |
Article |
