Augmenting approach for some maximum set problems

DOI10.1016/j.disc.2016.03.009zbMath1337.05083OpenAlexW2342695705MaRDI QIDQ284765

Ngoc C. Lê

Publication date: 18 May 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2016.03.009

zbMATH Keywords

independent setinduced matching\(k\)-regular induced subgraphaugmenting graphdissociative setfeedback vertex covernode-deletion problemvertex \(k\)-path cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• On finding augmenting graphs
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• The node-deletion problem for hereditary properties is NP-complete
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Induced matchings
• On maximum induced matchings in bipartite graphs
• Minimum \(k\)-path vertex cover
• Maximum \(k\)-regular induced subgraphs
• TWO THEOREMS IN GRAPH THEORY
• On F-independence in graphs
• Node-Deletion NP-Complete Problems
• Node-Deletion Problems on Bipartite Graphs
• Stable sets for (P_{6}, K_{2,3})-free graphs
• Paths, Trees, and Flowers
• Node-and edge-deletion NP-complete problems

This page was built for publication: Augmenting approach for some maximum set problems