Buchumschlag

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Duan, Hongyi, Zhang, Jian'an
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Geometry
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Worst-Case and Smoothed Analysis of the Hartigan-Wong Method for k-Means Clustering
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
von: Maus, Victor, et al.
Veröffentlicht: (2026)

Sparse Outerstring Graphs Have Logarithmic Treewidth
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

Finding a Largest-Area Triangle in a Terrain in Near-Linear Time
von: Cabello, Sergio, et al.
Veröffentlicht: (2021)

Scattering and Sparse Partitions, and their Applications
von: Filtser, Arnold
Veröffentlicht: (2020)

On Sparse Covers of Minor Free Graphs, Low Dimensional Metric Embeddings, and other applications
von: Filtser, Arnold
Veröffentlicht: (2024)

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
von: Mazziane, Younes Ben, et al.
Veröffentlicht: (2024)

Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
von: Depian, Thomas, et al.
Veröffentlicht: (2026)

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
von: Duraj, Lech, et al.
Veröffentlicht: (2023)

Local Routing on Ordered $Θ$-graphs
von: van Renssen, André, et al.
Veröffentlicht: (2025)

Dynamic Connectivity in Disk Graphs
von: Baumann, Alexander, et al.
Veröffentlicht: (2021)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
von: de Berg, Mark, et al.
Veröffentlicht: (2026)

Dynamic Locality Sensitive Orderings in Doubling Metrics
von: La, An, et al.
Veröffentlicht: (2024)

Unit-length Rectangular Drawings of Graphs
von: Alegria, Carlos, et al.
Veröffentlicht: (2022)

Clustered Planarity Variants for Level Graphs
von: Fink, Simon D., et al.
Veröffentlicht: (2024)

Computing Maximum Cliques in Unit Disk Graphs
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2025)

Parameterized Geometric Graph Modification with Disk Scaling
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Shortest Path Separators in Unit Disk Graphs
von: Harb, Elfarouk, et al.
Veröffentlicht: (2024)

Beyond Worst Case Local Computation Algorithms
von: Biswas, Amartya Shankha, et al.
Veröffentlicht: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2025)

Morphing Planar Graph Drawings Through 3D
von: Buchin, Kevin, et al.
Veröffentlicht: (2022)

Ranking and Unranking of the Planar Embeddings of a Planar Graph
von: Di Battista, Giuseppe, et al.
Veröffentlicht: (2024)

Learning with Structure: Computing Consistent Subsets on Structurally-Regular Graphs
von: Banik, Aritra, et al.
Veröffentlicht: (2025)

Single-Source Shortest Path Problem in Weighted Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2025)

Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2025)

An Improved Algorithm for Shortest Paths in Weighted Unit-Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2024)

Maximum Independent Sets in Disk Graphs with Disks in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

Computing Dominating Sets in Disk Graphs with Centers in Convex Position
von: Tkachenko, Anastasiia, et al.
Veröffentlicht: (2026)

ETH-Tight Algorithm for Cycle Packing on Unit Disk Graphs
von: An, Shinwoo, et al.
Veröffentlicht: (2024)

On Optimal Coreset Construction for Euclidean $(k,z)$-Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2022)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
von: Bhore, Sujoy, et al.
Veröffentlicht: (2025)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
von: S, Ajaykrishnan E, et al.
Veröffentlicht: (2025)

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

Computing Diameter +1 in Truly Subquadratic Time for Unit-Disk Graphs
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2024)

Small Independent Sets versus Small Separator in Geometric Intersection Graphs
von: Marin, Malory, et al.
Veröffentlicht: (2026)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
von: Koana, Tomohiro, et al.
Veröffentlicht: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
von: Chan, Timothy M., et al.
Veröffentlicht: (2026)

Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
von: Biedl, Therese, et al.
Veröffentlicht: (2026)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
von: Chan, Timothy M., et al.
Veröffentlicht: (2025)