Abstrakt. Med tanke på ett heltal viktat bipartite graf {G = (U V, E), w : E → Z} vi anser att problemen med att hitta alla kanter som förekommer i vissa minsta vikt matchning av maximal kardinalitet och räkna alla minsta vikt perfekt matchningar. Dessutom konstruerar vi en undergraf Gcs of G som är beroende av en optimal lösning av det dubbla linjära programmet kopplat till uppdragsproblem på {G, w} som gör att vi kan reducera dessa problem till deras ovägda varianter på Gcs. När till exempel G har en perfekt matchning och vi har en optimal lösning av det dubbla linjära programmet kopplat till uppdragsproblem på {G, w}, löser vi problemet med att hitta alla kanter som förekommer i någon minsta vikt perfekt matchning i linjär tid på antalet kanter. Därför får vi från början en algoritm som löser detta problem i tid O( н nm log(nW )), där n =  på U  på ≥  och V, m =  på plats, och W = max{ på plats (e) : e  på plats E}.
För bipartite grafer, Valencia och Vargas REF studerade den viktade versionen av detta problem som ber att hitta alla kanter som hör till någon minimum vikt perfekt matchning.
Optimum matchings in weighted bipartite graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}