En kant färgning av en multigraph är nästan rättvis om, bland kanterna incident till varje vertex, antalet kanter färgade med två färger skiljer sig med högst två. Det har bevisats att problemet med att hitta en nästan rättvis kant färgning kan lösas i O(m 2 /k) tid, där m och k är antalet kanter och givna färger, respektive. I detta dokument presenterar vi en rekursiv algoritm som körs i O (mn log (m/(kn) + 1)) tid, där n är antalet hörn. Denna algoritm förbättrar den mest kända värsta fall-tids komplexiteten. När k = O(1) är tid komplexiteten hos alla kända algoritmer är O(m 2 ), vilket innebär att denna tid komplexitet återstår att vara bäst i mer än tjugo år sedan 1982 när Hilton och de Werra gav ett konstruktivt bevis för förekomsten av en nästan rättvis kant färgning för alla multigrafer. Vårt resultat är det första som förbättrar denna tid komplexitet när m/n växer till oändlighet; t.ex., m = n  och för en godtycklig konstant  på > 1.
Observera att problemet med att bestämma förekomsten av en rättvis kant färgning är NP-fullständig (se REF ).
An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
{'venue': 'J. Graph Algorithms Appl.', 'journal': 'J. Graph Algorithms Appl.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}