Repozytorium publikacji - Politechnika Gdańska

Rozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.

Autorzy

• dr inż. Adrian Kosowski link otwiera się w nowej karcie ,
• dr hab. inż. Michał Małafiejski link otwiera się w nowej karcie ,
• Paweł Żyliński