Andreas Emil Feldmann

CoRR, 2024

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs.

[BibT_eX]

[DOI]

Michael Lampis

CoRR, 2024

2023

Parameterized Inapproximability of Independent Set in H-Free Graphs.

[BibT_eX]

[DOI]

Pavel Dvorák

Ashutosh Rai

Pawel Rzazewski

Algorithmica, April, 2023

Approximation Algorithms and Lower Bounds for Graph Burning.

[BibT_eX]

[DOI]

Matej Lieskovský

Jirí Sgall

Proceedings of the Approximation, 2023

2022

Generalized k-Center: Distinguishing Doubling and Highway Dimension.

[BibT_eX]

[DOI]

Tung Anh Vu

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

The Parameterized Complexity of the Survivable Network Design Problem.

[BibT_eX]

[DOI]

Anish Mukherjee

Erik Jan van Leeuwen

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension.

[BibT_eX]

[DOI]

Johannes Blum

Siddharth Gupta

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

2021

Parameterized Approximation Algorithms for Bidirected Steiner Network Problems.

[BibT_eX]

[DOI]

Pasin Manurangsi

ACM Trans. Algorithms, 2021

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices.

[BibT_eX]

[DOI]

Pavel Dvorák

SIAM J. Discret. Math., 2021

A note on the approximability of deepest-descent circuit steps.

[BibT_eX]

[DOI]

Steffen Borgwardt

Cornelius Brand

Martin Koutecký

Oper. Res. Lett., 2021

Polynomial time approximation schemes for clustering in low highway dimension graphs.

[BibT_eX]

[DOI]

David Saulpic

J. Comput. Syst. Sci., 2021

Near-linear Time Approximation Schemes for Clustering in Doubling Metrics.

[BibT_eX]

[DOI]

Vincent Cohen-Addad

David Saulpic

J. ACM, 2021

Travelling on Graphs with Small Highway Dimension.

[BibT_eX]

[DOI]

Algorithmica, 2021

Efficient fully dynamic elimination forests with applications to detecting long paths and cycles.

[BibT_eX]

[DOI]

Jiehua Chen

Wojciech Czerwinski

Bartlomiej Wróblewski

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On Extended Formulations For Parameterized Steiner Trees.

[BibT_eX]

[DOI]

Ashutosh Rai

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020

Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions).

[BibT_eX]

[DOI]

Rajesh Hemant Chitnis

Mohammad Taghi Hajiaghayi

Dániel Marx

SIAM J. Comput., 2020

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms.

[BibT_eX]

[DOI]

Karthik C. S.

Euiwoong Lee

Pasin Manurangsi

Electron. Colloquium Comput. Complex., 2020

On Dynamic Parameterized k-Path.

[BibT_eX]

[DOI]

Jiehua Chen

Wojciech Czerwinski

Bartlomiej Wróblewski

CoRR, 2020

The Parameterized Hardness of the k-Center Problem in Transportation Networks.

[BibT_eX]

[DOI]

Dániel Marx

Algorithmica, 2020

Recoloring Interval Graphs with Limited Recourse Budget.

[BibT_eX]

[DOI]

Bartlomiej Bosek

Jakub Pawlewicz

Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem.

[BibT_eX]

[DOI]

Davis Issac

Ashutosh Rai

Proceedings of the 15th International Symposium on Parameterized and Exact Computation, 2020

2019

Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2019

A Tight Lower Bound for Planar Steiner Orientation.

[BibT_eX]

[DOI]

Ondrej Suchý

Algorithmica, 2019

FPT Inapproximability of Directed Cut and Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics.

[BibT_eX]

[DOI]

David Saulpic

Vincent Cohen-Addad

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

A (1+ε)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.

[BibT_eX]

[DOI]

Wai Shing Fung

Ian Post

SIAM J. Comput., 2018

A Tight Lower Bound for Steiner Orientation.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2018

2017

Parameterized Approximation Algorithms for Directed Steiner Network Problems.

[BibT_eX]

[DOI]

Pasin Manurangsi

CoRR, 2017

2016

Lehman's Theorem and the Directed Steiner Tree Problem.

[BibT_eX]

[DOI]

Ahmad Abdi

Bertrand Guenin

Laura Sanità

SIAM J. Discret. Math., 2016

On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree.

[BibT_eX]

[DOI]

Neil Olver

Laura Sanità

Math. Program., 2016

Fast Approximation Algorithms for the Generalized Survivable Network Design Problem.

[BibT_eX]

[DOI]

Kanstantsin Pashkovich

Laura Sanità

Proceedings of the 27th International Symposium on Algorithms and Computation, 2016

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems.

[BibT_eX]

[DOI]

Dániel Marx

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Improving the Hk-bound on the price of stability in undirected Shapley network design games.

[BibT_eX]

[DOI]

Matús Mihalák

Theor. Comput. Sci., 2015

On the Parameterized Complexity of Computing Balanced Partitions in Graphs.

[BibT_eX]

[DOI]

René van Bevern

Manuel Sorge

Ondrej Suchý

Theory Comput. Syst., 2015

An O(n4) Time Algorithm to Compute the Bisection Width of Solid Grid Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2015

Balanced Partitions of Trees and Applications.

[BibT_eX]

[DOI]

Luca Foschini

Algorithmica, 2015

2013

Fast balanced partitioning is hard even on grids and trees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Corner cuts are close to optimal: From solid grids to polygons and back.

[BibT_eX]

[DOI]

Shantanu Das

Discret. Appl. Math., 2013

On the Parameterized Complexity of Computing Graph Bisections.

[BibT_eX]

[DOI]

René van Bevern

Manuel Sorge

Ondrej Suchý

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2013

Improving the H k -Bound on the Price of Stability in Undirected Shapley Network Design Games.

[BibT_eX]

[DOI]

Matús Mihalák

Proceedings of the Algorithms and Complexity, 8th International Conference, 2013

2012

Balanced partitioning of grids and related graphs: a theoretical study of data distribution in parallel finite element model simulations.

[BibT_eX]

[DOI]

PhD thesis, 2012

Computing approximate Nash equilibria in network congestion games.

[BibT_eX]

[DOI]

Heiko Röglin

Berthold Vöcking

Networks, 2012

Improving the $H_k$-Bound on the Price of Stability in Undirected Shapley Network Design Games

[BibT_eX]

[DOI]

Matús Mihalák

CoRR, 2012

2011

Fast Balanced Partitioning of Grid Graphs is Hard

[BibT_eX]

[DOI]

CoRR, 2011

Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons.

[BibT_eX]

[DOI]

Shantanu Das

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids.

[BibT_eX]

[DOI]

Shantanu Das