On the König deficiency of zero-reducible graphs

DOI10.1007/s10878-019-00466-2zbMath1434.05119OpenAlexW2987505511MaRDI QIDQ2292142

Miklós Bartha, Miklós Krész

Publication date: 3 February 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-019-00466-2

zbMATH Keywords

graph algorithmindependent setgraph matchinggraph reductionKönig property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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) Connectivity (05C40)

Related Items (1)

Data Reduction for Maximum Matching on Real-World Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• Graphs with equal independence and annihilation numbers
• A linear-time algorithm for a special case of disjoint set union
• Matching theory
• Critical independent sets and König-Egerváry graphs
• Tutte type theorems for graphs having a perfect internal matching
• Unique Maximum Matching Algorithms
• Near-optimal fully-dynamic graph connectivity
• Efficiency of a Good But Not Linear Set Union Algorithm
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• Paths, Trees, and Flowers

This page was built for publication: On the König deficiency of zero-reducible graphs