scientific article; zbMATH DE number 7236474

DOI10.4230/LIPIcs.SoCG.2018.70zbMath1489.68374arXiv1712.04595MaRDI QIDQ5116530

Vijay Sridhar, Kritika Singhal, Anastasios Sidiropoulos

Publication date: 18 August 2020

Full work available at URL: https://arxiv.org/abs/1712.04595

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

treewidthlower boundsfractal dimensionspannersexponential time hypothesis

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Fractals (28A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On Geometric Set Cover for Orthants

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The carving-width of generalized hypercubes
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• A sparse graph almost as good as the complete graph on points in \(k\) dimensions
• Measured descent: A new embedding method for finite metrics
• The black-box complexity of nearest-neighbor search
• The Online Metric Matching Problem for Doubling Metrics
• Approximating TSP on Metrics with Bounded Global Growth
• Searching dynamic point sets in spaces with bounded doubling dimension
• Polynomial Bounds for the Grid-Minor Theorem
• An Optimal Dynamic Spanner for Doubling Metric Spaces
• Finding nearest neighbors in growth-restricted metrics
• Bypassing the embedding
• Algorithmic Interpretations of Fractal Dimension
• The limited blessing of low dimensionality
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• The traveling salesman problem
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Algorithms – ESA 2005
• Small hop-diameter sparse spanners for doubling metrics