The labeled maximum matching problem

DOI10.1016/J.COR.2008.05.012zbMATH Open1179.90318OpenAlexW2075574301MaRDI QIDQ1000970FDOQ1000970

Authors Francesco Carrabs, Raffaele Cerulli, Monica Gentili

Publication date 12 February 2009

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2008.05.012

zbMATH Keywords

matchingbranch and boundexact approachlabelcolor

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms and Computation
• The labeled perfect matching in bipartite graphs
• A parallel branch and bound algorithm for the maximum labelled clique problem
• Efficient labelling algorithms for the maximum noncrossing matching problem
• On the completeness of a generalized matching problem

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1445322 (Why is no real title available?)
• A note on the minimum label spanning tree.
• Algorithms and Computation
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Comparison of heuristics for the colourful travelling salesman problem
• Heuristic approaches for the Minimum Labelling Hamiltonian Cycle Problem
• Introduction to algorithms
• Local search for the minimum label spanning tree problem with bounded color classes.
• On the minimum label spanning tree problem
• Paths, Trees, and Flowers
• Spanning trees with many or few colors in edge-colored graphs
• The Colorful Traveling Salesman Problem
• The labeled perfect matching in bipartite graphs
• The minimum labeling spanning trees
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem

Cited in

(13)

• The rainbow Steiner tree problem
• Two heuristics for the rainbow spanning forest problem
• On the complexity of rainbow spanning forest problem
• The Maximum Labeled Path Problem
• Minimum <scp>color‐degree</scp> perfect b‐matchings
• Graph Drawing
• Algorithms and Computation
• Bi-criteria and approximation algorithms for restricted matchings
• The rainbow spanning forest problem
• Uncertain vertex coloring problem
• Comparison of metaheuristics for the \(k\)-labeled spanning forest problem
• Maximum matchings of a digraph based on the largest geometric multiplicity
• A hybrid metaheuristic for the minimum labeling spanning tree problem

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: The labeled maximum matching problem

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