Open AccessAlgorithms for Weighted Matching Generalizations II: f-factors and the Special Case of Shortest Paths
Author(s) -
Harold N. Gabow,
Piotr Sankowski
Publication year - 2021
Publication title -
siam journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.533
H-Index - 122
eISSN - 1095-7111
pISSN - 0097-5397
DOI - 10.1137/16m1106225
Subject(s) - combinatorics , mathematics , exponent , omega , matching (statistics) , shortest path problem , discrete mathematics , binary logarithm , randomized algorithm , graph , philosophy , statistics , quantum mechanics , linguistics , physics
For an undirected graph or multigraph $G=(V,E)$ and a function $f:V\to \mathbb{Z_+}$, an $f$-factor is a subgraph whose degree function is $f$. For integral edge weights of maximum magnitude $W$ ou...
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom