A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem

DOI10.1016/J.COR.2013.04.009MaRDI QIDQ336528zbMATH OpenOpenAlexFDO

Authors Ioannis T. Christou, Spyridon Vassilaras

Publication date 10 November 2016

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

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

zbMATH Keywords

capacitybranch and boundoptimization methodsparallel algorithmsgraspmaximum distance-2 matchingwireless ad-hoc networks

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) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• An optimal parallel algorithm for maximal matching
• A two-stage parallel branch and bound algorithm for mixed integer programs
• An improvement on parallel computation of a maximal matching
• An improved parallel algorithm for maximal matching
• Parallelization of a branch-and-bound algorithm for the maximum weight clique problem
• An efficient parallel algorithm for maximum matching for some classes of graphs
• Publication:4489037
• Planar Maximum Matching: Towards a Parallel Algorithm
• A parallel branch and bound algorithm for the quadratic assignment problem

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 2114409 (Why is no real title available?)
• scientific article; zbMATH DE number 1420901 (Why is no real title available?)
• A probabilistic heuristic for a computationally difficult set covering problem
• Conflict analysis in mixed integer programming
• Distance-2-matchings of random graphs
• Distance-\(k\) knowledge in self-stabilizing algorithms
• Evolutionary Credibility Theory
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• NP-completeness of some generalizations of the maximum matching problem
• New results on induced matchings
• On the approximability of the maximum induced matching problem
• The strong chromatic index ofC4-free graphs

Cited in

(3)

• Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem
• Moderately exponential time algorithms for the maximum induced matching problem
• Parallel computational optimization in operations research: a new integrative framework, literature review and research directions

Describes a project that uses

Uses Software

• GRASP
• SCIP

This page was built for publication: A parallel hybrid greedy branch and bound scheme for the maximum distance-2 matching problem

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