Inapproximability results for graph convexity parameters

DOI10.1016/J.TCS.2015.06.059MaRDI QIDQ496002zbMATH OpenOpenAlexFDO

Authors Erika M. M. Coelho, Mitre C. Dourado, Rudini M. 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

zbMATH Keywords

APX-hardnessgeodesic convexityhull numberRadon number\(P_3\)-convexityinapproximability resultsCarathéodory number

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Convex partitions of graphs induced by paths of order three
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Irreversible conversion of graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On geodetic sets formed by boundary vertices
• On local convexity in graphs
• On the Carathéodory number for the convexity of paths of order three
• On the Carathéodory number of interval and graph convexities
• On the Radon number for \(P _{3}\)-convexity
• On the convexity number of graphs
• On the convexity of paths of length two in undirected graphs
• 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
• Some remarks on the geodetic number of a graph
• Structure preserving reductions among convex optimization problems
• The hull number of a graph

Cited in

(11)

• 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
• Inapproximability results and bounds for the Helly and Radon numbers of a graph
• On the parameterized complexity of the geodesic hull number
• Inapproximability results for graph convexity parameters
• Bootstrap percolation in strong products of graphs
• The hull number in the convexity of induced paths of order \(3\)
• The convexity of induced paths of order three and applications: complexity aspects

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)