Critical sets, crowns and local maximum independent sets
DOI10.1007/s10898-021-01094-zzbMath1504.05219arXiv2008.04587OpenAlexW3210797779MaRDI QIDQ2149605
Eugen Mandrescu, Vadim E. Levit
Publication date: 29 June 2022
Published in: Journal of Global Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.04587
bipartite graphmatchingcritical setcrownKönig-Egerváry graphgreedoidaugmentoidlocal maximum independent set
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local maximum stable set greedoids stemming from very well-covered graphs
- Crowns in bipartite graphs
- A characterization of the graphs in which the transversal number equals the matching number
- The critical independence number and an independence decomposition
- Greedoids
- A combinatorial structure ensuring applicability of the dynamic programming method
- A greedy algorithm for hereditary set systems and a generalization of the Rado-Edmonds characterization of matroids
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- Combinatorial properties of the family of maximum stable sets of a graph
- Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings
- Correspondence between two antimatroid algorithmic characterizations
- Very well covered graphs
- A new greedoid: The family of local maximum stable sets of a forest
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Critical independent sets and König-Egerváry graphs
- On maximum matchings in König-Egerváry graphs
- Using critical sets to solve the maximum independent set problem
- Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids
- Crown structures for vertex cover kernelization
- Crown reductions for the minimum weighted vertex cover problem
- On the corona of two graphs
- An algorithmic characterization of antimatroids
- Introduction to Greedoids
- Vertex packings: Structural properties and algorithms
- On Finding Critical Independent and Vertex Sets
- Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems
- A parallel algorithm for computing the critical independence number and related sets
- Some covering concepts in graphs
- Uniquely restricted matchings
This page was built for publication: Critical sets, crowns and local maximum independent sets
