En kant ranking av en graf är en begränsad färgning av kanterna med heltal. Det kräver att varje stig mellan två kanter med samma etikett i innehåller en mellankant med etikett j > i. En kantrankning är optimal om den använder minst antal olika etiketter bland alla möjliga kantrankningar. Den senaste forskningen har visat att problemet med att hitta en optimal kantrankning när den begränsas till träd medger en polynom-tid lösning, men komplexiteten i problemet för allmänna grafer har förblivit öppen i litteraturen. I detta papper visar vi att hitta en optimal kant ranking av en graf är NP-hård. Vi visar också att även hitta en någorlunda liten kant ranking är ogenomförbar i vissa fall. 0 1998 Elsevier Science B.V. Alla rättigheter förbehållna.
Det är faktiskt känt att för allmänna grafer, hitta en optimal kant ranking är NP-hård REF.
Edge ranking of graphs is hard
{'venue': 'Discret. Appl. Math.', 'journal': 'Discret. Appl. Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}