11 citations · 23 across the 16 of their papers we have counts for
Showing cs.DMShow all
3 papers · 1 filter
cs.DM2019
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…
cs.DM2019
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 …
cs.DM2018★ 7 cited
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…