Abstract
W pracy przedstawiono dowód faktu, że spójna szerokość ścieżkowa grafu wynosi co najwyżek 2k+1, gdzie k jest jego szerokością ścieżkową. Dowód jest konstruktywny, tzn., został skonstruowany algorytm, który dla podanej na wejściu dekompozycji grafu o szerekości k zwraca dekompozycję spóją o szerekości co najwyżej 2k+1.
Citations
-
1 9
CrossRef
-
0
Web of Science
-
2 3
Scopus
Author (1)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
SIAM JOURNAL ON DISCRETE MATHEMATICS
no. 26,
pages 1709 - 1732,
ISSN: 0895-4801 - Language:
- English
- Publication year:
- 2012
- Bibliographic description:
- Dereniowski D.: From Pathwidth to Connected Pathwidth// SIAM JOURNAL ON DISCRETE MATHEMATICS. -Vol. 26, nr. iss. 4 (2012), s.1709-1732
- DOI:
- Digital Object Identifier (open in new tab) 10.1137/110826424
- Verified by:
- Gdańsk University of Technology
seen 81 times
Recommended for you
On the complexity of distributed graph coloring with local minimality constraints
- C. Gavoille,
- R. Klasing,
- A. Kosowski
- + 2 authors
2009