On the König deficiency of zero-reducible graphs

DOI10.1007/S10878-019-00466-2MaRDI QIDQ2292142zbMATHzbMATHOpenAlexFDO

Authors Miklós Bartha, Miklós Krész

Publication date 3 February 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

graph matchinggraph algorithmindependent setgraph reductionKönig property

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On reduced zero-divisor graphs of posets
• Publication:5750892
• On Realizing Zero-Divisor Graphs
• Grundy domination and zero forcing in Kneser graphs
• Reduced zero-divisor graphs of posets
• On zero divisor graphs
• Irredundance and domination in kings graphs
• On domination in zero-divisor graphs
• On deficiency problems for graphs
• On \(\alpha^{+}\)-stable König-Egerváry graphs

Cites work

• scientific article; zbMATH DE number 48095 (Why is no real title available?)
• scientific article; zbMATH DE number 3202997 (Why is no real title available?)
• scientific article; zbMATH DE number 3211575 (Why is no real title available?)
• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Computing unique maximum matchings in \(O(m)\) time for König-Egerváry graphs and unicyclic graphs
• Critical independent sets and König-Egerváry graphs
• Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments
• Deterministic soliton graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• Graphs with equal independence and annihilation numbers
• Matching theory
• Near-optimal fully-dynamic graph connectivity
• Paths, Trees, and Flowers
• Tutte type theorems for graphs having a perfect internal matching
• Unique maximum matching algorithms

Cited in

(1)

• Data Reduction for Maximum Matching on Real-World Graphs

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

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