Fundamentals of Computation Theory

DOI10.1007/b11926zbMath1278.68098OpenAlexW2249105474MaRDI QIDQ5900783

Janka Chlebíková, Miroslav Chlebík

Publication date: 20 April 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/b11926

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Optimizing budget allocation for center and median points ⋮ Hardness and approximation results for packing Steiner trees ⋮ Approximation hardness of edge dominating set problems ⋮ Using VNS for the optimal synthesis of the communication tree in wireless sensor networks ⋮ Approximation and inapproximability results for maximum clique of disc graphs in high dimensions ⋮ Approximating Nash social welfare under binary XOS and binary subadditive valuations ⋮ Computing the minimum number of hybridization events for a consistent evolutionary history ⋮ On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ On the complexity of computing the temporal hybridization number for two phylogenies ⋮ Simultaneous matchings: Hardness and approximation ⋮ On the hardness of range assignment problems ⋮ Packing triangles in low degree graphs and indifference graphs ⋮ Commitment under uncertainty: Two-stage stochastic matching problems ⋮ On the approximability of the maximum induced matching problem

This page was built for publication: Fundamentals of Computation Theory