Augmenting approach for some maximum set problems

DOI10.1016/J.DISC.2016.03.009MaRDI QIDQ284765zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• An augmentation algorithm for the maximum weighted stable set problem
• scientific article; zbMATH DE number 2246590
• A Linear Time Approach to the Set Maxima Problem
• On the maximum capacity augmentation algorithm for the maximum flow problem
• scientific article; zbMATH DE number 1303581
• Near-optimal solutions for the generalized max-controlled set problem
• The maximum feasible subset problem (maxFS) and applications
• An Improved Approximation Algorithm for the Matching Augmentation Problem
• The Generalized Max-Controlled Set Problem
• Augmenting trail theorem for the maximum 1-2 matching problem

Cites work

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

Cited in

(4)

• Augmenting graphs for independent sets
• scientific article; zbMATH DE number 20270 (Why is no real title available?)
• scientific article; zbMATH DE number 2246590 (Why is no real title available?)
• Combinatorics and algorithms for augmenting graphs

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

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