Vertex cover at distance on H-free graphs

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

Authors: Clément Dallard, Mirza Krbezlija, Martin Milanič 

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_5\)-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
• 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_6\)-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
• H-free graphs, independent sets, and subexponential-time algorithms
• 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 \(r\)-dominating and \(2r\)-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)