From matchings to independent sets
From MaRDI portal
Publication:2403787
DOI10.1016/j.dam.2016.04.012zbMath1369.05174OpenAlexW2346400836MaRDI QIDQ2403787
Publication date: 12 September 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/78744/7/WRAP_m2i-revision.pdf
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Maximum weight independent set for \(\ell\)claw-free graphs in polynomial time ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time ⋮ Maximum independent sets in subcubic graphs: new results ⋮ Independent sets in \((P_4+P_4\),triangle)-free graphs
Cites Work
- Unnamed Item
- Stability preserving transformations of graphs
- Maximum regular induced subgraphs in \(2P_3\)-free graphs
- Pseudo-Boolean optimization
- Augmenting graphs for independent sets
- On finding augmenting graphs
- A magnetic procedure for the stability number
- Matching theory
- On diameters and radii of bridged graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Computing independent sets in graphs with large girth
- Stability number of bull- and chair-free graphs
- Stable sets in certain \(P_6\)-free graphs
- Path parity and perfection
- On the use of Boolean methods for the computation of the stability number
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Struction revisited
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- A transformation which preserves the clique number
- Crown structures for vertex cover kernelization
- Augmenting chains in graphs without a skew star.
- TWO THEOREMS IN GRAPH THEORY
- A measure & conquer approach for the analysis of exact algorithms
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Paths, Trees, and Flowers
- Characterizations of derived graphs
- A Computing Procedure for Quantification Theory
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
This page was built for publication: From matchings to independent sets
