DagSemProc.07211.2.pdf
- Filesize: 107 kB
- 4 pages
Document
Linear-time certifying recognition for partitioned probe cographs
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 7211
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2007-12-14
Cite AsGet BibTex
Van Bang Le and H.N. de Ridder. Linear-time certifying recognition for partitioned probe cographs. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
https://doi.org/10.4230/DagSemProc.07211.2
https://doi.org/10.4230/DagSemProc.07211.2
Abstract
Cographs are those graphs without induced path on four vetices. A graph $G=(V, E)$ with a partition $V=Pcup N$ where $N$ is an independent set is a partitioned probe cograph if one can add new edges between certain vertices in $N$ in such a way that the graph obtained is a cograph. We characterize partitioned probe cographs in terms of five forbidden induced subgraphs. Using this characterization, we give a linear-time recognition algorithm for partitioned probe cographs. Our algorithm produces a certificate for membership that can be checked in linear time and a certificate for non-membership that can be checked in sublinear time.
Keywords
- Cograph
- probe cograph
- certifying graph algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads