Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs

DOI10.1016/j.cor.2017.06.006zbMath1391.90622OpenAlexW2622841700MaRDI QIDQ1652405

Gilbert Laporte, Sanne Wøhlk

Publication date: 11 July 2018

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

Full work available at URL: https://pure.au.dk/ws/files/141709447/W_hlk2017_Computational_Comparison_of_Several_Greedy_Algorithms_AM.pdf

zbMATH Keywords

rural postman problemcapacitated arc routing problemgarbage collectionblossom algorithmperfect matching problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Mixed integer programming (90C11) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Temporal matching on geometric graph data ⋮ Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments ⋮ Temporal matching

Uses Software

• CPLEX
• Blossom V
• Blossom IV

Cites Work

• Unnamed Item
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Tour splitting algorithms for vehicle routing problems
• An Approximation Algorithm for the Capacitated Arc Routing Problem
• Fast and Simple Algorithms for Weighted Perfect Matching
• Approximation Algorithms for Some Postman Problems
• Computing Minimum-Weight Perfect Matchings
• A Tabu Search Heuristic for the Capacitated arc Routing Problem
• Paths, Trees, and Flowers

This page was built for publication: Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs