Inapproximability results for graph convexity parameters
DOI10.1016/J.TCS.2015.06.059zbMATH Open1329.68122OpenAlexW796183652MaRDI QIDQ496002FDOQ496002
Mitre C. Dourado, Rudini M. Sampaio, Erika M. M. Coelho
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
Recommendations
- Inapproximability results for graph convexity parameters
- Inapproximability results and bounds for the Helly and Radon numbers of a graph
- Inapproximability results related to monophonic convexity
- The convexity of induced paths of order three and applications: complexity aspects
- On the convexity number of graphs
APX-hardnessgeodesic convexityhull numberRadon number[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Carath%EF%BF%BD%EF%BF%BDodory+number&go=Go Carath��odory number]\(P_3\)-convexityinapproximability results
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On local convexity in graphs
- Title not available (Why is that?)
- Structure preserving reductions among convex optimization problems
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the convexity number of graphs
- On the Carathéodory Number for the Convexity of Paths of Order Three
- Title not available (Why is that?)
- Irreversible conversion of graphs
- Some remarks on the geodetic number of a graph
- The hull number of a graph
- On the geodetic Radon number of grids
- On the hull number of some graph classes
- On the hull number of triangle-free graphs
- On two-path convexity in multipartite tournaments
- Some remarks on simple tournaments
- On the Carathéodory number of interval and graph convexities
- On geodetic sets formed by boundary vertices
- On the Radon Number for P 3-Convexity
- On the convexity of paths of length two in undirected graphs
- Graphs with few \(P_4\)'s under the convexity of paths of order three
Cited In (8)
- Convex and isometric domination of (weak) dominating pair graphs
- On the \(P_3\)-hull number of some products of graphs
- On the \(P_3\)-hull numbers of \(q\)-Kneser graphs and Grassmann graphs
- On the \(P_3\)-hull number of Kneser graphs
- Computing the hull number in toll convexity
- On the parameterized complexity of the geodesic hull number
- Bootstrap percolation in strong products of graphs
- The hull number in the convexity of induced paths of order \(3\)
This page was built for publication: Inapproximability results for graph convexity parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q496002)
