11 citations · 23 across the 16 of their papers we have counts for
20 papers
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…
A Polynomial Coreset for Furthest Neighbor in Planar Metrics
Kacper Kluk, Hung Le, Wojciech Nadara +3
A furthest neighbor data structure on a metric space and a set answers the following query: given , output maximizing $\mathr…
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…
Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
Romain Bourneuf, Jana Masaříková, Wojciech Nadara +1
For a fixed integer , a (-)long claw, denoted , is the unique tree with three leaves, each at distance exactly from the vertex of degree three. Majewski…
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…
Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík +3
We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain vertex-disjoint cycles, then it suffices to delete vertices to obta…
Decreasing the maximum average degree by deleting an independent set or a d-degenerate subgraph
Wojciech Nadara, Marcin Smulewicz
The maximum average degree of a graph is the maximum average degree over all subgraphs of . In this paper we prove that for every and positive integer…
Improved bounds for the excluded-minor approximation of treedepth
Wojciech Czerwiński, Wojciech Nadara, Marcin Pilipczuk
Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant …
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…
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich +2
The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary f…