4 papers · 1 filter
Partially Dynamic Algorithms for Single-Source Temporal Paths
Davide Bilò, Bartłomiej Bosek, Jadwiga Czyżewska +3
We present efficient partially dynamic algorithms for maintaining earliest arrival times from a fixed source in temporal digraphs with vertices. For the incremental scenario wh…
Dynamic data structures for twin-ordered matrices
Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…
QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
Édouard Bonnet, Jadwiga Czyżewska, Tomáš Masařík +2
We present a quasipolynomial-time approximation scheme (QPTAS) for the Maximum Independent Set (\textsc{MWIS}) in graphs with a bounded number of pairwise vertex-disjoint and non-a…
A note on finding long directed cycles above the minimum degree bound in 2-connected digraphs
Jadwiga Czyżewska, Marcin Pilipczuk
For a directed graph , let be the minimum among in-degrees and out-degrees of all vertices of . It is easy to see that contains a directed cycle of l…