Back to Search
Start Over
Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs.
- Source :
- Graph-Theoretic Concepts in Computer Science (9783540241324); 2004, p93-104, 12p
- Publication Year :
- 2004
-
Abstract
- This paper presents an optimal fully-dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in $\mathcal{O}(d)$ time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular tree decomposition is updated; otherwise, a certificate is returned within the same complexity. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783540241324
- Database :
- Supplemental Index
- Journal :
- Graph-Theoretic Concepts in Computer Science (9783540241324)
- Publication Type :
- Book
- Accession number :
- 32701106