New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
From MaRDI portal
Publication:5091022
DOI10.4230/LIPIcs.ISAAC.2018.31OpenAlexW2908394031MaRDI QIDQ5091022
Guanlan Tan, Qilong Feng, Senmin Zhu, Jianxin Wang, Bin Fu
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2018.31
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Altruistically unbalanced kidney exchange
- Combinatorial and spectral properties of König-Egerváry graphs
- A characterization of the graphs in which the transversal number equals the matching number
- The complexity of König subgraph problems and above-guarantee vertex cover
- Almost 2-SAT is fixed-parameter tractable
- Ear-decompositions of matching-covered graphs
- Matching theory
- Independence numbers of graphs - an extension of the Koenig-Egervary theorem
- A 2-approximation algorithm for the minimum weight edge dominating set problem
- On two extensions of equimatchable graphs
- König-Egerváry graphs, 2-bicritical graphs and fractional matchings
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- Critical independent sets and König-Egerváry graphs
- A kernel of order \(2k-c\log k\) for vertex cover
- On approximability of optimization problems related to red/blue-split graphs
- Two more characterizations of König-Egerváry graphs
- A new kernel for parameterized Max-Bisection above tight lower bound
- Forbidden subgraphs and the König-Egerváry property
- On maximum matchings in König-Egerváry graphs
- On Multiway Cut Parameterized above Lower Bounds
- Paths, Flowers and Vertex Cover
- Subgraph characterization of red/blue-split graph and kőnig egerváry graphs
- König Deletion Sets and Vertex Covers above the Matching Size
- A 3/2-Approximation Algorithm for General Stable Marriage
- Raising The Bar For V<scp>ertex</scp> C<scp>over</scp>: Fixed-parameter Tractability Above A Higher Guarantee
- A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter
- Faster Parameterized Algorithms Using Linear Programming
- Reducibility among Combinatorial Problems
- Bisections above Tight Lower Bounds
- Efficient partnership formation in networks
- Paths, Trees, and Flowers
- Approximation and intractability results for the maximum cut problem and its variants
- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number
- Improved Parameterized Upper Bounds for Vertex Cover
This page was built for publication: New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition
