1 citations · 1 across the 4 of their papers we have counts for
6 papers · 1 filter
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…
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee +1
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We surve…
Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
Andreas Emil Feldmann, Davis Issac, Ashutosh Rai
We develop an FPT algorithm and a bi-kernel for the Weighted Edge Clique Partition (WECP) problem, where a graph with vertices and integer edge weights is given together with a…
FPT Inapproximability of Directed Cut and Connectivity Problems
Rajesh Chitnis, Andreas Emil Feldmann
(see paper for full abstract) Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a se…
Travelling on Graphs with Small Highway Dimension
Yann Disser, Andreas Emil Feldmann, Max Klimm +1
We study the Travelling Salesperson (TSP) and the Steiner Tree problem (STP) in graphs of low highway dimension. This graph parameter was introduced by Abraham et al. [SODA 2010] a…
Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics
Vincent Cohen-Addad, Andreas Emil Feldmann, David Saulpic
We consider the classic Facility Location, -Median, and -Means problems in metric spaces of doubling dimension . We give nearly linear-time approximation schemes for each…