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 general graph is NP-complete. This paper presents an algorithm for computing the treewidth and constructing a corresponding tree-decomposition for circular-arc graphs in $O( n^3 )$ time.
Publication Year: 1994
Publication Date: 1994-11-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 43
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot