Computing and Combinatorics
DOI10.1007/11533719zbMATH Open1128.68398OpenAlexW4376561447MaRDI QIDQ5716992FDOQ5716992
Authors: Jean Cardinal, Martine Labbé, Stefan Langerman, Eythan Levy, Hadrien Mélot 
Publication date: 11 January 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11533719
Recommendations
- Hardness and approximation of minimum maximal matchings
- Tight approximation ratio for Minimum Maximal Matching
- scientific article; zbMATH DE number 4116586
- Performance analysis of greedy algorithms for Max-IS and Min-Maxl-Match
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (14)
- Connected Vertex Covers in Dense Graphs
- Improved approximation bounds for edge dominating set in dense graphs
- Minimum maximal matchings in cubic graphs
- A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
- Facet defining inequalities among graph invariants: The system graphedron
- Connected vertex covers in dense graphs
- Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
- Integer programming formulations for the minimum weighted maximal matching problem
- Bounding and approximating minimum maximal matchings in regular graphs
- A general class of heuristics for minimum weight perfect matching and fast special cases with doubly and triply logarithmic errors
- Approximating edge dominating set in dense graphs
- Why Locally-Fair Maximal Flows in Client-Server Networks Perform Well
- Approximating edge dominating set in dense graphs
- Why locally-fair maximal flows in client-server networks perform well
This page was built for publication: Computing and Combinatorics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5716992)
