From Pathwidth to Connected Pathwidth

Dariusz Dereniowski

doi:10.1137/110826424

From Pathwidth to Connected Pathwidth

Abstrakt

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.

Cytowania

1 9

CrossRef
0

Web of Science
2 3

Scopus

Autor (1)

Dariusz Dereniowski prof. dr hab. inż.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: SIAM JOURNAL ON DISCRETE MATHEMATICS nr 26, strony 1709 - 1732,
ISSN: 0895-4801
Język:: angielski
Rok wydania:: 2012
Opis bibliograficzny:: Dereniowski D.: From Pathwidth to Connected Pathwidth// SIAM JOURNAL ON DISCRETE MATHEMATICS. -Vol. 26, nr. iss. 4 (2012), s.1709-1732
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1137/110826424
Weryfikacja:: Politechnika Gdańska