Cover Image

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Xu, Chao, Yang, Mingdong
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
by: Doron-Arad, Ilan, et al.
Published: (2023)

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
by: Ansaripour, Matin, et al.
Published: (2024)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
by: Gavva, Surya Teja, et al.
Published: (2025)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, et al.
Published: (2026)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
by: Haeupler, Bernhard, et al.
Published: (2025)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
by: Kurita, Kazuhiro, et al.
Published: (2022)

Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
by: Ahrens, Willow
Published: (2020)

Bicriteria Algorithms for Submodular Cover with Partition and Fairness Constraints
by: Chen, Wenjing, et al.
Published: (2026)

Max-Cut with Multiple Cardinality Constraints
by: Makarychev, Yury, et al.
Published: (2025)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)

Diameter Computation on (Random) Geometric Graphs
by: Bläsius, Thomas, et al.
Published: (2026)

Going Beyond Surfaces in Diameter Approximation
by: Włodarczyk, Michał
Published: (2025)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Streaming Diameter of High-Dimensional Points
by: Halldórsson, Magnús M., et al.
Published: (2025)

Diameter Shortcut Sets on Temporal Graphs
by: Quantmeyer, Gerome
Published: (2025)

An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies
by: Chen, Yike, et al.
Published: (2024)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

Computing Experiment-Constrained D-Optimal Designs
by: Pillai, Aditya, et al.
Published: (2024)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
by: Sun, Ming, et al.
Published: (2022)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

Breaking the Quadratic Barrier: Robust Cardinality Sketches for Adaptive Queries
by: Cohen, Edith, et al.
Published: (2025)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

Algorithmic Problems in Categories of Partitions
by: Faroß, Nicolas, et al.
Published: (2025)

New Structures and Algorithms for Length-Constrained Expander Decompositions
by: Haeupler, Bernhard, et al.
Published: (2024)

Cardinality-Constrained Continuous Knapsack Problem with Concave Piecewise-Linear Utilities
by: Bai, Miao, et al.
Published: (2023)

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
by: Gadekar, Ameet, et al.
Published: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Dynamic Diameter in High-Dimensions against Adaptive Adversary and Beyond
by: Banihashem, Kiarash, et al.
Published: (2025)

Optimal Extended Formulations from Optimal Dynamic Programming Algorithms
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Capacitated Partition Vertex Cover and Partition Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

Effective Index Construction Algorithm for Optimal $(k,η)$-cores Computation
by: Sun, Shengli, et al.
Published: (2025)

Approximation Algorithms for Hop Constrained and Buy-at-Bulk Network Design via Hop Constrained Oblivious Routing
by: Chekuri, Chandra, et al.
Published: (2024)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)