Maximal viktmatchning

Inom datavetenskap och grafteori är problemet med maximal viktmatchning problemet med att hitta, i en viktad graf , en matchning där summan av vikter är maximerad.

Ett specialfall av det är tilldelningsproblemet , där inmatningen är begränsad till att vara en tvådelad graf , och matchningen är begränsad till att ha kardinalitet som för den minsta av de två partitionerna. Ett annat specialfall är problemet med att hitta en maximal kardinalitetsmatchning på en oviktad graf: detta motsvarar fallet där alla kantvikter är desamma.

Algoritmer

Det finns en $O(V^{2}E)$ tidsalgoritm för att hitta en maximal matchning eller en maximal viktmatchning i en graf som inte är tvådelad; det beror på Jack Edmonds , kallas för vägar, träd och blommor- metoden eller helt enkelt Edmonds algoritm , och använder dubbelriktade kanter . En generalisering av samma teknik kan också användas för att hitta maximala oberoende uppsättningar i klofria grafer .

Mer utarbetade algoritmer finns och granskas av Duan och Pettie (se tabell III). Deras arbete föreslår en approximationsalgoritm för det maximala viktmatchningsproblemet, som körs i linjär tid för alla fasta felgränser.