2026-07-22T13:49:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19356 2024-03-06T11:03:51Z ddc:004 open_access

Connected Vertex Cover on AT-Free Graphs Mukherjee, Joydeep Saha, Tamojit Graph Algorithm AT-free graphs Connected Vertex Cover Optimization Asteroidal Triple (AT) in a graph is an independent set of three vertices such that every pair of them has a path between them avoiding the neighbourhood of the third. A graph is called AT-free if it does not contain any asteroidal triple. A connected vertex cover of a graph is a subset of its vertices which contains at least one endpoint of each edge and induces a connected subgraph. Settling the complexity of computing a minimum connected vertex cover in an AT-free graph was mentioned as an open problem in Escoffier et al. [Escoffier et al., 2010]. In this paper we answer the question by presenting an exact polynomial time algorithm for computing a minimum connected vertex cover problem on AT-free graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joydeep Mukherjee and Tamojit Saha 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.54 urn:nbn:de:0030-drops-193566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.54 eng https://creativecommons.org/licenses/by/4.0/legalcode