Get all the updates for this publication
Conferences
Treewidth of circular-arc graphs+Published in Springer Verlag
1991
DOI: 10.1007/BFb0028248
Volume: 519 LNCS
The treewidth of a graph is one of the most important graph-theoretic parameters from the algorithm point of view. However, computing 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 cicular-arc graphs in O(n4) time. © Springer-Verlag Berlin Heidelberg 1991.
Content may be subject to copyright.
Related Papers (3)
ConferencesTowards Measuring Quality of Service in Untrusted Multi-Vendor Service Function Chains: Balancing Security and Resource Consumption2019 | Institute of Electrical and Electronics Engineers Inc.- ConferencesData Subsetting: A Data-Centric Approach to Approximate Computing2019 | Institute of Electrical and Electronics Engineers Inc.
About the journal
| Journal | Data powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Publisher | Data powered by TypesetSpringer Verlag |
| ISSN | 03029743 |
| Open Access | No |
Authors (1)
C Pandu Rangan- Perfectly secure message transmission in directed networks tolerating threshold and non threshold adversary
- Perfectly reliable and secure communication in directed networks tolerating mixed adversary
- Optimal parallel algorithms on circular-arc graphs
- Group key establishment (GKE): Two/three party key exchange to GKE
Concepts (9)
Data structures- Graph theory
- CIRCULAR-ARC GRAPH
- GENERAL GRAPH
- Graph-theoretic
- Np complete
- TREE DECOMPOSITION
- Tree-width
- Trees (mathematics)
