Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Miroslav Chlebík

dblp:55/5774 · DBLP profile ↗
← Back
18ranked-venue papers
18as first author
0since 2021 · last 2019
0000-0001-8137-479XORCID · verified

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 18 · 18 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
2 papers
Computational complexity · 42% Computational geometry · 33% Graph algorithms and graph theory · 25%

Topics — the 4 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity
hardness of approximation
0.122008
Approximation hardness of dominating set problems in bounded degree graphs · Inf. Comput. 2008
Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes · SODA 2005
Graph algorithms and graph theory
dominating set
0.112008
Approximation hardness of dominating set problems in bounded degree graphs · Inf. Comput. 2008
Computational geometry
intersection graphs
0.112005
Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes · SODA 2005
Computational geometry › intersection graphs
rectangle intersection graphs
0.112005
Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes · SODA 2005

Methods — techniques the papers use, named apart from their topics

reduction · 0.1
YearPublicationVenuePosition
2019 Approximation Hardness of Travelling Salesman via Weighted Amplifiers
Miroslav Chlebík, Janka Chlebíková
COCOON1
2014 Connection between conjunctive capacity and structural properties of graphs
Miroslav Chlebík, Janka Chlebíková
Theor. Comput. Sci.1
2013 On the Conjunctive Capacity of Graphs
Miroslav Chlebík, Janka Chlebíková
COCOON1
2008 Crown reductions for the Minimum Weighted Vertex Cover problem
Miroslav Chlebík, Janka Chlebíková
Discret. Appl. Math.1
2008 Approximation hardness of dominating set problems in bounded degree graphs
Miroslav Chlebík, Janka Chlebíková
Inf. Comput.1
2008 The Steiner tree problem on graphs: Inapproximability results
Miroslav Chlebík, Janka Chlebíková
Theor. Comput. Sci.1
2007 Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover
Miroslav Chlebík, Janka Chlebíková
Discret. Appl. Math.1
2007 The Complexity of Combinatorial Optimization Problems on d-Dimensional Boxes
abstract
The MAXIMUM INDEPENDENT SET problem in d‐box graphs, i.e., in intersection graphs of axis‐parallel rectangles in $\mathbb{R}^d$, is known to be NP‐hard for any fixed $d\geq 2$. A challenging open problem is that of how closely the solution can be approximated by a polynomial time algorithm. For the restricted case of d‐boxes with bounded aspect ratio a PTAS exists [T. Erlebach, K. Jansen, and E. Seidel, SIAM J. Comput., 34 (2005), pp. 1302–1323]. In the general case no polynomial time algorithm with approximation ratio $o(\log^{d-1} n)$ for a set of n d‐boxes is known. In this paper we prove APX‐hardness of the MAXIMUM INDEPENDENT SET problem in d‐box graphs for any fixed $d\geq 3$. We give an explicit lower bound $\frac{245}{244}$ on efficient approximability for this problem unless $\PP=\text{\rm NP}$. Additionally, we provide a generic method how to prove APX‐hardness for other graph optimization problems in d‐box graphs for any fixed $d\geq 3$.
Miroslav Chlebík, Janka Chlebíková
SIAM J. Discret. Math.1
2006 Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
Miroslav Chlebík, Janka Chlebíková
CIAC1
2006 Hard coloring problems in low degree planar bipartite graphs
Miroslav Chlebík, Janka Chlebíková
Discret. Appl. Math.1
2006 Complexity of approximating bounded variants of optimization problems
Miroslav Chlebík, Janka Chlebíková
Theor. Comput. Sci.1
2005 Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
Miroslav Chlebík, Janka Chlebíková
SODA1
2004 Approximation Hardness of Dominating Set Problems
Miroslav Chlebík, Janka Chlebíková
ESA1
2004 On Approximation Hardness of the Minimum 2SAT-DELETION Problem
Miroslav Chlebík, Janka Chlebíková
MFCS1
2004 On Approximability of the Independent Set Problem for Low Degree Graphs
Miroslav Chlebík, Janka Chlebíková
SIROCCO1
2003 Approximation Hardness for Small Occurrence Instances of NP-Hard Problems
Miroslav Chlebík, Janka Chlebíková
CIAC1
2003 Inapproximability Results for Bounded Variants of Optimization Problems
Miroslav Chlebík, Janka Chlebíková
FCT1
2003 Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching
Miroslav Chlebík, Janka Chlebíková
ISAAC1