Computing and Combinatorics

DOI10.1007/11533719MaRDI QIDQ5716992zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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)

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

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
• Facet defining inequalities among graph invariants: The system graphedron
• Connected vertex covers in dense graphs
• A $(2 - c \frac{\log {n}}{n})$ Approximation Algorithm for the Minimum Maximal Matching Problem
• 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)