2026-07-25T01:58:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1270 2024-03-06T11:07:33Z ddc:004 open_access

Linear-time certifying recognition for partitioned probe cographs Le, Van Bang de Ridder, H.N. Cograph probe cograph certifying graph algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Van Bang Le and H.N. de Ridder 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07211.2 urn:nbn:de:0030-drops-12703 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.2 eng https://creativecommons.org/licenses/by/4.0/legalcode