Cover Image

Faster exponential algorithms for cut problems via geometric data structures

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Kozma, László, Tan, Junqi
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

Balanced TSP partitioning
by: Berendsohn, Benjamin Aram, et al.
Published: (2025)

Online sorting and online TSP: randomized, stochastic, and high-dimensional
by: Abrahamsen, Mikkel, et al.
Published: (2024)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, et al.
Published: (2023)

Theoretical Analysis of Byte-Pair Encoding
by: Kozma, László, et al.
Published: (2024)

Even Faster Algorithm for the Chamfer Distance
by: Feng, Ying, et al.
Published: (2025)

Improved space-time tradeoff for TSP via extremal set systems
by: Dallant, Justin, et al.
Published: (2026)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Compact representations of pattern-avoiding permutations
by: Kozma, László, et al.
Published: (2025)

Computing crossing numbers with topological and geometric restrictions
by: Hamm, Thekla, et al.
Published: (2024)

Faster Goal-Oriented Shortest Path Search for Bulk and Incremental Detailed Routing
by: Ahrens, Markus, et al.
Published: (2021)

Non-adaptive Bellman-Ford: Yen's improvement is optimal
by: Hu, Jialu, et al.
Published: (2024)

Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-and-Bifurcate Technique
by: Chan, Timothy M., et al.
Published: (2025)

Parameterized and approximation algorithms for coverings points with segments in the plane
by: Kowalska, Katarzyna, et al.
Published: (2024)

Dynamic parameterized problems on unit disk graphs
by: An, Shinwoo, et al.
Published: (2024)

Spanner for the $0/1/\infty$ weighted region problem
by: Gudmundsson, Joachim, et al.
Published: (2024)

A new near-linear time algorithm for k-nearest neighbor search using a compressed cover tree
by: Elkin, Yury, et al.
Published: (2021)

Approximation Algorithms for Smallest Intersecting Balls
by: Zheng, Jiaqi, et al.
Published: (2024)

Compressed data structures for Heegaard splittings
by: Ennes, Henrique, et al.
Published: (2025)

Optimization with pattern-avoiding input
by: Berendsohn, Benjamin Aram, et al.
Published: (2023)

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Hashing geographical point data using the space-filling H-curve
by: Netay, Igor V.
Published: (2024)

Maintaining Light Spanners via Minimal Updates
by: Khodabandeh, Hadi, et al.
Published: (2024)

Time complexity of the Analyst's Traveling Salesman algorithm
by: Ramirez, Anthony, et al.
Published: (2022)

Retroactive Monotonic Priority Queues via Range Searching
by: Castro, Lucas, et al.
Published: (2025)

Euclidean distance compression via deep random features
by: Leroux, Brett, et al.
Published: (2024)

Relating Interleaving and Fréchet Distances via Ordered Merge Trees
by: Beurskens, Thijs, et al.
Published: (2023)

Triangle Detection in Worst-Case Sparse Graphs via Local Sketching
by: Duan, Hongyi, et al.
Published: (2025)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
by: Bhore, Sujoy, et al.
Published: (2024)

Scalable Exact Hierarchical Agglomerative Clustering via Sparse Geographic Distance Graphs
by: Maus, Victor, et al.
Published: (2026)

Single-Criteria Metric $r$-Dominating Set Problem via Minor-Preserving Support
by: Browne, Reilly, et al.
Published: (2026)

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

An Improved FPT Algorithm for Computing the Interleaving Distance between Merge Trees via Path-Preserving Maps
by: P V, Althaf, et al.
Published: (2026)

An algorithm for accurate and simple-looking metaphorical maps
by: Katsanou, Eleni, et al.
Published: (2025)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
by: Gribanov, D., et al.
Published: (2023)

Light Spanners with Small Hop-Diameter
by: Bhore, Sujoy, et al.
Published: (2025)

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
by: Depian, Thomas, et al.
Published: (2025)

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

FPT Constant Approximation Algorithms for Colorful Sum of Radii
by: Liu, Shuilian, et al.
Published: (2025)

Tight Universal Bounds for Partially Presorted Pareto Front and Convex Hull
by: van der Hoog, Ivor, et al.
Published: (2025)