Cover Image

Approximating Densest Subgraph in Geometric Intersection Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Har-Peled, Sariel, Saladi, Rahul
Format:	Preprint
Published:	2024
Subjects:	Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximately: Independence Implies Vertex Cover
by: Har-Peled, Sariel
Published: (2023)

Proof of Dudley's Convex Approximation
by: Har-Peled, Sariel, et al.
Published: (2019)

A Practical Approach for Computing the Diameter of a Point Set
by: Har-Peled, Sariel
Published: (2025)

The Complexity of One or Many Faces in the Overlay of Many Arrangements
by: Har-Peled, Sariel
Published: (2025)

An Output Sensitive Algorithm for Discrete Convex Hulls
by: Har-Peled, Sariel
Published: (2026)

Separator for $c$-Packed Segments and Curves
by: Har-Peled, Sariel
Published: (2026)

A Simple Proof of the Existence of a Planar Separator
by: Har-Peled, Sariel
Published: (2011)

How to Get Close to the Median Shape
by: Har-Peled, Sariel
Published: (2026)

The Prophet and the Voronoi Diagram
by: Har-Peled, Sariel
Published: (2026)

Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
by: Barequet, Gill, et al.
Published: (2025)

Bifurcation: How to Explore a Tree
by: Har-Peled, Sariel
Published: (2025)

Fast Approximation Algorithms for Piercing Boxes by Points
by: Agarwal, Pankaj K., et al.
Published: (2023)

How Packed Is It, Really?
by: Har-Peled, Sariel, et al.
Published: (2021)

Polygon Containment and Translational Min-Hausdorff-Distance between Segment Sets are 3SUM-Hard
by: Barequet, Gill, et al.
Published: (2025)

Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems
by: Har-Peled, Sariel, et al.
Published: (2014)

Near-Optimal Euclidean Locality-Sensitive Orderings
by: Gao, Zhimeng, et al.
Published: (2023)

In the Search for Good Neck Cuts
by: Ruggerio, Sam, et al.
Published: (2026)

The Fréchet Distance Unleashed: Approximating a Dog with a Frog
by: Har-Peled, Sariel, et al.
Published: (2024)

Dependable Spanners via Unreliable Edges
by: Har-Peled, Sariel, et al.
Published: (2024)

Improving the average dilation of a metric graph by adding edges
by: Har-Peled, Sariel, et al.
Published: (2025)

No-dimensional Tverberg Partitions Revisited
by: Har-Peled, Sariel, et al.
Published: (2023)

New Constructions of SSPDs and their Applications
by: Abam, Mohammad A., et al.
Published: (2025)

Orthogonal Emptiness Queries for Random Points
by: Dullerud, Jonathan E., et al.
Published: (2025)

Well-Separated Pairs Decomposition Revisited
by: Har-Peled, Sariel, et al.
Published: (2025)

The Road to the Closest Point is Paved by Good Neighbors
by: Har-Peled, Sariel, et al.
Published: (2025)

Graph-Based Nearest-Neighbor Search without the Spread
by: Giliberti, Jeff, et al.
Published: (2026)

An Easy Proof of a Weak Version of Chernoff inequality
by: Har-Peled, Sariel
Published: (2025)

Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
by: Nekrich, Yakov, et al.
Published: (2026)

On Small Pair Decompositions for Point Sets
by: Buchin, Kevin, et al.
Published: (2026)

A Bouquet of Results on Maximum Range Sum: General Techniques and Hardness Reductions
by: Gusain, Rachana, et al.
Published: (2025)

Oracle-Augmented Prophet Inequalities
by: Har-Peled, Sariel, et al.
Published: (2024)

Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
by: Kisfaludi-Bak, Sándor, et al.
Published: (2026)

Quickly Avoiding a Random Catastrophe
by: Ashur, Stav, et al.
Published: (2025)

Hop-Spanners for Geometric Intersection Graphs
by: Conroy, Jonathan B., et al.
Published: (2021)

Further Results on Rendering Geometric Intersection Graphs Sparse by Dispersion
by: Honorato-Droguett, Nicolás, et al.
Published: (2025)

Partial Domination in Some Geometric Intersection Graphs and Some Complexity Results
by: Dutta, Madhura, et al.
Published: (2025)

Two Results on LPT: A Near-Linear Time Algorithm and Parcel Delivery using Drones
by: Chandran, L. Sunil, et al.
Published: (2024)

Sparse Bounded Hop-Spanners for Geometric Intersection Graphs
by: Bhore, Sujoy, et al.
Published: (2025)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
by: Marin, Malory, et al.
Published: (2025)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)