From Pathwidth to Connected Pathwidth

Dariusz Dereniowski

doi:10.1137/110826424

From Pathwidth to Connected Pathwidth

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)

Dariusz Dereniowski prof. dr hab. inż.

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 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