Wyszukiwarka
Abstrakt
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.
Cytowania
-
7
CrossRef
-
0
Web of Science
-
7
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie z listy filadelfijskiej
- Opublikowano w:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
nr 14,
strony 63 - 86,
ISSN: 1382-6905 - Język:
- angielski
- Rok wydania:
- 2007
- Opis bibliograficzny:
- Kosowski A., Małafiejski M., Żyliński P.: Packing [1,Delta]-factors in graphs of small degree // JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 14., nr. nr 1 (2007), s.63-86
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1007/s10878-006-9034-4
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 91 razy