Connected vertex cover for \((sP_1+P_5)\)-free graphs

DOI10.1007/s00453-019-00601-9zbMath1436.68245OpenAlexW2964093597MaRDI QIDQ5919305

Giacomo Paesani, Daniël Paulusma, Matthew Johnson

Publication date: 16 January 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/28406/1/28406.pdf

zbMATH Keywords

polynomial-time algorithmvertex coverconnected vertex coverH-free graph

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Feedback Vertex Set and Even Cycle Transversal for $H$-Free Graphs: Finding Large Block Graphs ⋮ Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Induced disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ Contracting to a longest path in H-free graphs ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Computing subset transversals in \(H\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• A new characterization of \(P_k\)-free graphs
• The price of connectivity for cycle transversals
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Connected vertex covers in dense graphs
• Vertex and edge covers with clustering properties: Complexity and algorithms
• Partitioning graphs into connected parts
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Dominating cliques in \(P_ 5\)-free graphs
• Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• List coloring in the absence of a linear forest
• Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
• Boundary classes for graph problems involving non-local properties
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Choosability of P 5-Free Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Stable sets for (P_{6}, K_{2,3})-free graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• The Price of Connectivity for Vertex Cover
• Connected vertex cover for \((sP_1+P_5)\)-free graphs

This page was built for publication: Connected vertex cover for \((sP_1+P_5)\)-free graphs