scientific article; zbMATH DE number 2081000

MaRDI QIDQ4474098zbMATH OpenFDO

Authors Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov, Therese Biedl

Publication date 4 August 2004

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2223/22230308.htm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Tight bounds on maximal and maximum matchings
• Bounds on maximum \(b\)-matchings
• Tight lower bounds on the size of a maximum matching in a regular graph
• Matchability and \(k\)-maximal matchings
• Tight bound for matching
• Maximal tight sets and the Edmonds-Gallai decomposition for matchings
• Bounding and approximating minimum maximal matchings in regular graphs
• Truly Tight-in-Δ Bounds for Bipartite Maximal Matching and Variants
• Tight lower bounds on the matching number in a graph with given maximum degree
• Tight approximation ratio for Minimum Maximal Matching

Cited in

(20)

• On an estimate of the size of the maximum matching for a family of disjoint compact convex sets in the plane
• Tight lower bounds on the size of a maximum matching in a regular graph
• scientific article; zbMATH DE number 2185638 (Why is no real title available?)
• Factorially many maximum matchings close to the Erdős-Gallai bound
• Tight bound for matching
• Tight lower bounds on the matching number in a graph with given maximum degree
• Match-bounds revisited
• Hardness and approximation of minimum maximal matchings
• Lower Bounds for Maximal Matchings and Maximal Independent Sets
• On the complexity of minimum maximal uniquely restricted matching
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• A Min-Max Theorem for a Constrained Matching Problem
• A simply exponential upper bound on the maximum number of stable matchings
• Maximum Neighbour Voronoi Games
• scientific article; zbMATH DE number 1617264 (Why is no real title available?)
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• On the maximum 2-1 matching
• Erratum to: Tight bound for matching
• Tight bounds on maximal and maximum matchings
• Bounds on maximum \(b\)-matchings

This page was built for publication:

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