Matchings under distance constraints. I

DOI10.1007/S10479-021-04127-8MaRDI QIDQ2241576zbMATH OpenOpenAlexFDO

Authors Péter Madarasi

Publication date 9 November 2021

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10479-021-04127-8

zbMATH Keywords

approximation algorithmsconstrained matchingdistance matchingintegrality gapparameterized algorithmsrestricted \(b\)-matchingscheduling

Mathematics Subject Classification ID

Graph theory (05Cxx) Theory of computing (68Qxx) Mathematical programming (90Cxx)

Recommendations

• The distance matching problem
• Matchings under distance constraints. II.
• Constrained matching problems in bipartite graphs
• Simultaneous matchings: Hardness and approximation
• Matching with sizes (or scheduling with processing set restrictions)

Cites work

• A strongly polynomial minimum cost circulation algorithm
• Approximating maximum uniquely restricted matchings in bipartite graphs
• Connections in combinatorial optimization
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• List-coloring of interval graphs with application to register assignment for heterogeneous register-set architectures
• Models and solution techniques for frequency assignment problems
• On Maximum Cost $K_{t,t}$‐Free t‐Matchings of Bipartite Graphs
• On some hard and some tractable cases of the maximum acyclic matching problem
• Reducibility among combinatorial problems
• Restricted b-matchings in degree-bounded graphs
• Some Matching Problems for Bipartite Graphs
• The distance matching problem

Cited in

(2)

• Matchings under distance constraints. II.
• Prefix-bounded matrices

Describes a project that uses

Uses Software

• CALMA

This page was built for publication: Matchings under distance constraints. I

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