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

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

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)

Cites Work

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

Cited In (13)

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

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)