TREEWIDTH OF CIRCULAR-ARC GRAPHS

Authors
SUNDARAM R SINGH KS RANGAN CP
Citation
R. Sundaram et al., TREEWIDTH OF CIRCULAR-ARC GRAPHS, SIAM journal on discrete mathematics, 7(4), 1994, pp. 647-655
Citations number
14
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
7
Issue
4
Year of publication
1994
Pages
647 - 655
Database
ISI
SICI code
0895-4801(1994)7:4<647:TOCG>2.0.ZU;2-F
Abstract
The treewidth of a graph is one of the most important graph-theoretic parameters from the algorithmic point of view. However, computing the treewidth and constructing a corresponding tree-decomposition for a ge neral graph is NP-complete. This paper presents an algorithm for compu ting the treewidth and constructing a corresponding tree-decomposition for circular-are graphs in O(n(3)) time.