𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An extension of the bipartite weighted matching problem

✍ Scribed by Ai-Jia Hsieh; Chin-Wen Ho; Kuo-Chin Fan

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
446 KB
Volume
16
Category
Article
ISSN
0167-8655

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An extension of bipartite multigraphs
An extension of bipartite multigraphs
✍ D. De Werra πŸ“‚ Article πŸ“… 1976 πŸ› Elsevier Science 🌐 English βš– 702 KB

Usual edge colorings have been generalized in various ways; we wilI consider here essentially good edge colorings as well as equitable edge colorings. It is known that bipartite multigraphs present the property of having an equitable k-coloring for each k 3 2. This implies that they also have a good

A survey of heuristics for the weighted
A survey of heuristics for the weighted matching problem
✍ David Avis πŸ“‚ Article πŸ“… 1983 πŸ› John Wiley and Sons 🌐 English βš– 909 KB

This survey paper reviews results on heuristics for two weighted matching problems: matchings where the vertices are points in the plane and weights are Euclidean distances, and the assignment problem. Several heuristics are described in detail-and results are given for worst-case ratio bounds, abso

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ JiΕ™Γ­ Fiala πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co