An exact performance bound for an \(O(m+n)\) time greedy matching procedure

zbMATH Open0885.05092MaRDI QIDQ1378525

Andrew Shapira

Publication date: 12 February 1998

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: http://www.emis.de/journals/EJC/Volume_4/Abstracts/v4i1r25.html

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal problemsboundmaximum matchingextremal functionaugmenting path algorithmsgreedy matching procedure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

This page was built for publication: An exact performance bound for an \(O(m+n)\) time greedy matching procedure

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