Packing [1,Delta]-factors in graphs of small degree

Adrian Kosowski; Michał Małafiejski; Paweł Żyliński

doi:10.1007/s10878-006-9034-4

Packing [1,Delta]-factors in graphs of small degree

Abstract

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.

Citations

7

CrossRef
0

Web of Science
7

Scopus

Authors (3)

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

Keywords

Details

Category:: Articles
Type:: artykuł w czasopiśmie z listy filadelfijskiej
Published in:: JOURNAL OF COMBINATORIAL OPTIMIZATION no. 14, pages 63 - 86,
ISSN: 1382-6905
Language:: English
Publication year:: 2007
Bibliographic description:: 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:: Digital Object Identifier (open in new tab) 10.1007/s10878-006-9034-4
Verified by:: Gdańsk University of Technology