Near-linear-time algorithm for the geodetic Radon number of grids

DOI10.1016/J.DAM.2015.05.001MaRDI QIDQ299103zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado, V. G. Pereira de Sá, Dieter Rautenbach, Jayme L. Szwarcfiter

Publication date 22 June 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2015.05.001

zbMATH Keywords

geodetic convexitygraph convexitygridsRadon number

Mathematics Subject Classification ID

Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the geodetic Radon number of grids
• Algorithms and complexity for geodetic sets on partial grids
• scientific article; zbMATH DE number 1986052
• Bounds and algorithms for geodetic hulls
• An algorithm for non-matching grid projections with linear complexity
• Rapid and accurate computation of the distance function using grids
• On fast integration in geoid determination
• scientific article; zbMATH DE number 4009685
• A Fast Discrete Approximation Algorithm for the Radon Transform

Cites work

• Aspects of convexity and its applications
• Convexity and graph theory. Proceedings of the Conference on Convexity and Graph Theory, Israel, March 1981
• Der Satz von Radon in konvexen Produktstrukturen. II
• Geodesic Convexity in Graphs
• On the geodetic Radon number of grids
• Partition numbers for trees and ordered sets

Cited in

(7)

• On the \(P_3\)-hull number of some products of graphs
• On the geodetic Radon number of grids
• Geodetic convexity parameters for \((q, q - 4)\)-graphs
• Geodetic convexity parameters for graphs with few short induced paths
• On the monophonic rank of a graph
• Algorithms and complexity for geodetic sets on partial grids
• Tolerant Radon partitions of induced path convexity in graphs

This page was built for publication: Near-linear-time algorithm for the geodetic Radon number of grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q299103)