Vertex cover at distance on H-free graphs

DOI10.1007/978-3-030-79987-8_17MaRDI QIDQ2115860zbMATH OpenOpenAlexFDO

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

• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• A new characterization of \(P_k\)-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• Distance \(k\)-domination, distance \(k\)-guarding, and distance \(k\)-vertex cover of maximal outerplanar graphs
• Distance domination, guarding and covering of maximal outerplanar graphs
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Edge Dominating Sets in Graphs
• H-free graphs, independent sets, and subexponential-time algorithms
• Independent set in \(P_5\)-free graphs in polynomial time
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time
• Mim-width. III. Graph powers and generalized distance domination problems
• Minimum \(k\)-path vertex cover
• NP-completeness of some generalizations of the maximum matching problem
• New min-max theorems for weakly chordal and dually chordal graphs
• On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• On maximal independent sets of vertices in claw-free graphs
• On the minimum vertex \(k\)-path cover of trees
• On the vertex \(k\)-path cover
• PTAS for minimum \(k\)-path vertex cover in ball graph
• Partitioning a graph into small pieces with applications to path transversal
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Reducibility among combinatorial problems
• Relations between packing and covering numbers of a tree
• Structurally parameterized \(d\)-scattered set
• The k-Domination and k-Stability Problems on Sun-Free Chordal 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)