Janka Chlebíková

Niklas Paulsen

Theor. Comput. Sci., June, 2023

Safe Edges: A Study of Triangulation in Fill-in and Tree-Width Problems.

[BibT_eX]

[DOI]

Mani Ghahremani

CoRR, 2023

2022

Weighted amplifiers and inapproximability results for Travelling Salesman problem.

[BibT_eX]

[DOI]

J. Comb. Optim., 2022

2021

Colourful components in k-caterpillars and planar graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Degree-anonymization using edge rotations.

[BibT_eX]

[DOI]

Pierre Cazals

Theor. Comput. Sci., 2021

2020

Graphs without a partition into two proportionally dense subgraphs.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2020

How to Get a Degree-Anonymous Graph Using Minimum Number of Edge Rotations.

[BibT_eX]

[DOI]

Pierre Cazals

Proceedings of the Combinatorial Optimization and Applications, 2020

2019

Proportionally dense subgraph of maximum size: Complexity and approximation.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2019

Towards a Complexity Dichotomy for Colourful Components Problems on k-caterpillars and Small-Degree Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 30th International Workshop, 2019

Approximation Hardness of Travelling Salesman via Weighted Amplifiers.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 25th International Conference, 2019

Complexity of Scheduling for DARP with Soft Ride Times.

[BibT_eX]

[DOI]

Niklas Paulsen

Proceedings of the Algorithms and Complexity - 11th International Conference, 2019

2018

Structural and Algorithmic Properties of 2-Community Structures.

[BibT_eX]

[DOI]

Thomas Pontoizeau

Algorithmica, 2018

2017

The firefighter problem: Further steps in understanding its complexity.

[BibT_eX]

[DOI]

Morgan Chopin

Theor. Comput. Sci., 2017

2015

New Insight into 2-Community Structures in Graphs with Applications in Social Networks.

[BibT_eX]

[DOI]

Thomas Pontoizeau

Proceedings of the Combinatorial Optimization and Applications, 2015

2014

Connection between conjunctive capacity and structural properties of graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

2013

The Firefighter Problem: A Structural Analysis.

[BibT_eX]

[DOI]

Morgan Chopin

Electron. Colloquium Comput. Complex., 2013

On the Conjunctive Capacity of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 19th International Conference, 2013

2009

Hardness of approximation for orthogonal rectangle packing and covering problems.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2009

2008

The Steiner tree problem on graphs: Inapproximability results.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2008

Approximation hardness of dominating set problems in bounded degree graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2008

Crown reductions for the Minimum Weighted Vertex Cover problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2008

2007

The Complexity of Combinatorial Optimization Problems on d-Dimensional Boxes.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2007

A characterization of some graph classes using excluded minors.

[BibT_eX]

[DOI]

Period. Math. Hung., 2007

The d-precoloring problem for k-degenerate graphs.

[BibT_eX]

[DOI]

Klaus Jansen

Discret. Math., 2007

Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2007

2006

Complexity of approximating bounded variants of optimization problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2006

Assign ranges in general ad-hoc networks.

[BibT_eX]

[DOI]

Deshi Ye

Hu Zhang

J. Parallel Distributed Comput., 2006

Approximation hardness of edge dominating set problems.

[BibT_eX]

[DOI]

J. Comb. Optim., 2006

Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Hard coloring problems in low degree planar bipartite graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2006

Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 6th Italian Conference, 2006

2005

Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2004

On Approximability of the Independent Set Problem for Low Degree Graphs.

[BibT_eX]

[DOI]

Proceedings of the Structural Information and Communication Complexity, 2004

On Approximation Hardness of the Minimum 2SAT-DELETION Problem.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

Approximation Hardness of Dominating Set Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

2003

Inapproximability results for bounded variants of optimization problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 14th International Symposium, 2003

Approximation Hardness for Small Occurrence Instances of NP-Hard Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Complexity, 5th Italian Conference, 2003

2002

Approximation Hardness for Small Occurrence Instances of NP-Hard Problem

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

Partial k-trees with maximum chromatic number.

[BibT_eX]

[DOI]

Discret. Math., 2002

The structure of obstructions to treewidth and pathwidth.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2002

Approximation Hardness of the Steiner Tree Problem on Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2002

1996

Approximating the Maximally Balanced Connected Partition Problem in Graphs.

[BibT_eX]