𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dynamic matchings and quasidynamic fractional matchings. I

✍ Scribed by James B. Orlin

Publisher
John Wiley and Sons
Year
1983
Tongue
English
Weight
560 KB
Volume
13
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper presents and solves in polynomial time the dynamic matching problem, an integer programming problem which involves matchings in a time‐expanded infinite network. The initial model is a finite directed graph G = (V, E) in which each edge has an associated real‐valued weight and an integral distance. We wish to “match” vertices over an infinite horizon, and we permit vertex i in period p to be matched to vertex j in period r if and only if there is an edge e = (i, j) of E with distance r‐p or else an edge e = (j, i) of E with distance p‐r. Equivalently, we construct a “dynamic graph” in which there is an edge incident to vertex i‐p and to vertex j‐r in the above cases. The weight of this matched edge in the dynamic (time‐expanded) graph is the weight of e. The dynamic matching problem is to determine a matching M in the dynamic graph such that M has a maximum long‐run average weight per period. We show that the infinite horizon dynamic matching problem is linearly transformable to the finite horizon Q‐matching problem, which is shown to be solvable in polynomial time in Part II of this paper.

📜 SIMILAR VOLUMES

Dynamic matchings and quasidynamic fract
Dynamic matchings and quasidynamic fractional matchings. II
✍ James B. Orlin 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 869 KB

Consider a directed graph G in which every edge has an associated real-valued distance and a real-valued weight. The weight of an undirected circuit of C is the sum of the weights of the edges, whereas the distance of an undirected circuit is the sum of the distances of the forward edges of the circ

Perfect fractional matchings in random h
Perfect fractional matchings in random hypergraphs
✍ Michael Krivelevich 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 890 KB

Given an r-uniform hypergraph H = (V, E ) on ( V ( = n vertices, a real-valued function f(e) 5 1 for all u E V and C e E E f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n + m , at the very moment to when the last isolated

Maximal matchings in graphs with large n
Maximal matchings in graphs with large neighborhoods of independent vertices
✍ I. Rinsma; C. H. C. Little; D. R. Woodall 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB

## Abstract We obtain lower bounds on the size of a maximum matching in a graph satisfying the condition |__N(X)__| ≥ __s__ for every independent set __X__ of __m__ vertices, thus generalizing results of Faudree, Gould, Jacobson, and Schelp for the case __m__ = 2.