Automata, Languages and Programming

DOI10.1007/11523468zbMath1085.68112OpenAlexW2940595899WikidataQ56656999 ScholiaQ56656999MaRDI QIDQ5716851

George Karakostas

Publication date: 10 January 2006

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

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

An edge-reduction algorithm for the vertex cover problem ⋮ A primal-dual approximation algorithm for partial vertex cover: Making educated guesses ⋮ Minimum 2SAT-DELETION: Inapproximability results and relations to minimum vertex cover ⋮ On inverse traveling salesman problems ⋮ Graph covering using bounded size subgraphs ⋮ An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ Flip distance between triangulations of a planar point set is APX-hard ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ The 0-1 inverse maximum stable set problem ⋮ Vertex cover might be hard to approximate to within \(2 - \varepsilon \) ⋮ Minimum vertex cover in ball graphs through local search ⋮ A better list heuristic for vertex cover ⋮ Minimum vertex cover in rectangle graphs ⋮ Linear time algorithms for approximating the facility terminal cover problem ⋮ The multi‐integer set cover and the facility terminal cover problem ⋮ The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification ⋮ Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

This page was built for publication: Automata, Languages and Programming