Inapproximability Results for Graph Convexity Parameters

DOI10.1007/978-3-319-08001-7_9zbMath1416.68132OpenAlexW2183703932MaRDI QIDQ3188869

Erika M. M. Coelho, Mitre C. Dourado, Rudini Menezes Sampaio

Publication date: 2 September 2014

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08001-7_9

zbMATH Keywords

Carathéodory numberconvexity numberinterval numberAPX-hardnesshull numbergeodetic convexityRadon numberinapproximability results\(P _{3}\)-convexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results ⋮ The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects

This page was built for publication: Inapproximability Results for Graph Convexity Parameters