Inapproximability results for graph convexity parameters
From MaRDI portal
Publication:496002
DOI10.1016/j.tcs.2015.06.059zbMath1329.68122OpenAlexW796183652MaRDI QIDQ496002
Mitre C. Dourado, Erika M. M. Coelho, Rudini Menezes Sampaio
Publication date: 16 September 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.06.059
Carathéodory numbergeodesic convexityAPX-hardnesshull numberRadon number\(P_3\)-convexityinapproximability results
Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
On the \(P_3\)-hull number of some products of graphs, Computing the hull number in toll convexity, Convex and isometric domination of (weak) dominating pair graphs, On the parameterized complexity of the geodesic hull number, On the \(P_3\)-hull number of Kneser graphs, The hull number in the convexity of induced paths of order \(3\), On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the Carathéodory number of interval and graph convexities
- Graphs with few \(P_4\)'s under the convexity of paths of order three
- Irreversible conversion of graphs
- On geodetic sets formed by boundary vertices
- Some remarks on the geodetic number of a graph
- The hull number of a graph
- On local convexity in graphs
- Structure preserving reductions among convex optimization problems
- On the geodetic Radon number of grids
- On the convexity number of graphs
- On two-path convexity in multipartite tournaments
- Some remarks on simple tournaments
- On the Convexity of Paths of Length Two in Undirected Graphs
- On the Radon Number for P 3-Convexity
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On the Hull Number of Triangle-Free Graphs
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On the Carathéodory Number for the Convexity of Paths of Order Three
