HAL TEI export of lirmm-00108770 CCSD CC0 1.0 - Universal

HAL API Platform

 Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs Christophe Crespelle dab408c77ef7b16f90bcc0cc556a55a3 lirmm.fr 861830 405142-861830 Christophe Paul 8d0f2986f5075f135be0ba25be6c1ff9 lirmm.fr christophe-paul 4726 16049-4726 https://www.idref.fr/151101345 https://orcid.org/0000-0001-6519-975X Christine Carvalho De Matos 10103945d6df12b14430343989bb0f6f lirmm.fr 2006-10-23 12:55:43 2004 2024-03-08 20:57:38 2006-11-27 10:11:54 2004-06 2006-10-23 contributor Christine Carvalho De Matos 10103945d6df12b14430343989bb0f6f lirmm.fr CCSD lirmm-00108770 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108770 crespelle:lirmm-00108770 <i>WG 2004 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science</i>, Jun 2004, Bad Honnef, Germany. pp.93-104 WG 2004 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2004, Bad Honnef, Germany. pp.93-104 HAL Authorization CNRS - Centre national de la recherche scientifique Algorithmes, Graphes et Combinatoire Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier Mathématiques, Informatique, Physique et Systèmes Université de Montpellier Université de Montpellier (2015-2021) This paper presents an optimal fully-dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph $G$, the algorithm support arc and vertex modification (insertion or removal) 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. International No No Yes Yes Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs Christophe Crespelle dab408c77ef7b16f90bcc0cc556a55a3 lirmm.fr 861830 405142-861830 Christophe Paul 8d0f2986f5075f135be0ba25be6c1ff9 lirmm.fr christophe-paul 4726 16049-4726 https://www.idref.fr/151101345 https://orcid.org/0000-0001-6519-975X 10197 WG 2004 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science 2004-06 2004-06 Bad Honnef Germany Hromkovic J. Nagl M. Lecture Notes in Computer Science 3353 93-104 2004 English Dynamic algorithms Certifying algorithms Directed cographs Computer Science [cs]/Other [cs.OH] Conference papers Conference papers Conference papers

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 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 decomposition tree is updated; otherwise, a certificate is returned within the same complexity.

 139590827 0000000405990488 199111950H https://ror.org/013yean28 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LIRMM 1995-01-01 2021-12-31
161 rue Ada - 34095 Montpellier
https://www.lirmm.fr Algorithmes, Graphes et Combinatoire ALGCO 2021-12-31
LIRMM, 161 rue Ada, 34000 Montpellier
https://www.lirmm.fr/equipes/ALGCO/ 0000000120970141 https://ror.org/051escj72 Université de Montpellier UM 2021-12-31
163 rue Auguste Broussonnet - 34090 Montpellier
http://www.umontpellier.fr/ 02636817X 0000000122597504 https://ror.org/02feahw73 Centre National de la Recherche Scientifique CNRS 1939-10-19
https://www.cnrs.fr/