11 citations · 23 across the 16 of their papers we have counts for
14 papers · 1 filter
Dynamic domination and independence in sparse graphs
Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk +1
Let be a class of graphs of bounded expansion and be fixed. We give a dynamic data structure that for a given dynamic graph , updated by edge i…
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…
Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
In this paper, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most i…
Fully dynamic biconnectivity in time
Jacob Holm, Wojciech Nadara, Eva Rotenberg +1
We present a deterministic fully-dynamic data structure for maintaining information about the cut-vertices in a graph; i.e. the vertices whose removal would disconnect the graph. O…
A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees
Lars Jaffke, Paloma T. de Lima, Wojciech Nadara +1
Computing bounded depth decompositions is a bottleneck in many applications of the treedepth parameter. The fastest known algorithm, which is due to Reidl, Rossmanith, Sánchez Vill…
Exact Shortest Paths with Rational Weights on the Word RAM
Adam Karczmarz, Wojciech Nadara, Marek Sokołowski
Exact computation of shortest paths in weighted graphs has been traditionally studied in one of two settings. First, one can assume that the edge weights are real numbers and all t…
Fully dynamic approximation schemes on planar and apex-minor-free graphs
Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk +1
The classic technique of Baker [J. ACM '94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and…
Dynamic treewidth
Tuukka Korhonen, Konrad Majewski, Wojciech Nadara +2
We present a data structure that for a dynamic graph that is updated by edge insertions and deletions, maintains a tree decomposition of of width at most under the p…
Computing treedepth in polynomial space and linear fpt time
Wojciech Nadara, Michał Pilipczuk, Marcin Smulewicz
The treedepth of a graph is the least possible depth of an elimination forest of : a rooted forest on the same vertex set where every pair of vertices adjacent in is bou…
Determining 4-edge-connected components in linear time
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz +1
In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-e…
Approximating pathwidth for graphs of small treewidth
Carla Groenland, Gwenaël Joret, Wojciech Nadara +1
We describe a polynomial-time algorithm which, given a graph with treewidth , approximates the pathwidth of to within a ratio of . This is the first a…
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Jiehua Chen, Wojciech Czerwiński, Yann Disser +8
We present a data structure that in a dynamic graph of treedepth at most , which is modified over time by edge insertions and deletions, maintains an optimum-height elimination…
Many visits TSP revisited
Łukasz Kowalik, Shaohua Li, Wojciech Nadara +2
We study the Many Visits TSP problem, where given a number for each of cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that…
Experimental evaluation of kernelization algorithms to Dominating Set
Wojciech Nadara
The theoretical notions of graph classes with bounded expansion and that are nowhere dense are meant to capture structural sparsity of real world networks that can be used to desig…