Vertex cover at distance on H-free graphs

DOI10.1007/978-3-030-79987-8_17OpenAlexW3173980913MaRDI QIDQ2115860FDOQ2115860

Martin Milanič, Mirza Krbezlija, Clément Dallard

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-79987-8_17

zbMATH Keywords

polynomial-time algorithmdichotomy\(H\)-free graph\textsf{NP}-completenessdistance-\(k\) vertex cover

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Reducibility among Combinatorial Problems
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Minimum \(k\)-path vertex cover
• On the vertex \(k\)-path cover
• Independent Set in P₅-Free Graphs in Polynomial Time
• On maximal independent sets of vertices in claw-free graphs
• Title not available (Why is that?)
• Edge Dominating Sets in Graphs
• A new characterization of \(P_k\)-free graphs
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• NP-completeness of some generalizations of the maximum matching problem
• Relations between packing and covering numbers of a tree
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• New Min-Max Theorems for Weakly Chordal and Dually Chordal Graphs
• Distance domination, guarding and covering of maximal outerplanar graphs
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• On the minimum vertex \(k\)-path cover of trees
• On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
• Structurally parameterized \(d\)-Scattered Set
• Title not available (Why is that?)
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Partitioning a graph into small pieces with applications to path transversal
• Mim-width. III. Graph powers and generalized distance domination problems
• On distance ‐dominating and ‐independent sets in sparse graphs
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs

This page was built for publication: Vertex cover at distance on \(H\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115860)