Dariusz Dereniowski

Dariusz Dereniowski

Auto-generated profile, based on publicly available information

Dariusz Dereniowski

Gdansk University of Technology, Gdansk, Poland

Research Focus & Metrics

Academic Career Length

23Years (2004-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 August 2015 in Information and Computation
Verified
Journal Article
Closed access
DDDariusz Dereniowski
Dariusz Dereniowski
YDYann Disser
Yann Disser
AKAdrian Kosowski
Adrian Kosowski
DPDominik Pająk
Dominik Pająk
Przemysław UznańskiPrzemysław Uznański
Przemysław Uznański

1 February 2012 in Journal of Parallel and Distributed Computing
Verified
Journal Article
Closed access
DDDariusz Dereniowski
Dariusz Dereniowski
APAndrzej Pelc
Andrzej Pelc

1 July 2008 in Discrete Applied Mathematics
Verified
Journal Article
Closed access
DDDariusz Dereniowski
Dariusz Dereniowski

1 November 2015 in Theoretical Computer Science
Verified
Journal Article
Closed access
DDDariusz Dereniowski
Dariusz Dereniowski
DDDanny Dyer
Danny Dyer
RTRyan M. Tifenbach
Ryan M. Tifenbach
BYBoting Yang
Boting Yang

1 January 2012 in SIAM Journal on Discrete Mathematics
Verified
Journal Article
Closed access
DDDariusz Dereniowski
Dariusz Dereniowski
It is proven that the connected pathwidth of any graph $G$ is at most $2\cdot\textup{pw}(G)+1$, where $\textup{pw}(G)$ is the pathwidth of $G$. The method is constructive, i.e., it yields an efficient algorithm that for a given path decomposition of width $k$ computes a connected path decomposition of width at most $2k+1$. The running time of the algorithm is $O(dk^2)$, where $d$ is the number of “bags” in the input path decomposition. The motivation for studying connected path decompositions comes from the connection between the pathwidth and the search number of a graph. One of the advantages of the above bound for connected pathwidth is an inequality $\textup{\texttt{cs}}(G)\leq 2\textup{\texttt{s}}(G)+3$, where $\textup{\texttt{cs}}(G)$ and $\textup{\texttt{s}}(G)$ are the connected search number and the search number of $G$, respectively. Moreover, the algorithm presented in this work can be used to convert a given search strategy using $k$ searchers into a (monotone) connected one using $2k+3$ searchers and starting at an arbitrary homebase.

1 May 2006 in Information Processing Letters
Verified
Journal Article
Closed access
DDDariusz Dereniowski
Dariusz Dereniowski
ANAdam Nadolski
Adam Nadolski