Buchumschlag

Binary $k$-Center with Missing Entries: Structure Leads to Tractability

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Soheil, Farehe, Simonov, Kirill, Friedrich, Tobias
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Finding Minimum Distance Preservers: A Parameterized Study
von: Simonov, Kirill, et al.
Veröffentlicht: (2026)

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

Combining Crown Structures for Vulnerability Measures
von: Casel, Katrin, et al.
Veröffentlicht: (2024)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
von: Mallek, Nadym, et al.
Veröffentlicht: (2025)

Structural Parameterization of Steiner Tree Packing
von: Hastrich, Niko, et al.
Veröffentlicht: (2025)

Algorithmic Extensions of Dirac's Theorem
von: Fomin, Fedor V., et al.
Veröffentlicht: (2020)

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

Connected Partitions via Connected Dominating Sets
von: Niklanovits, Aikaterini, et al.
Veröffentlicht: (2025)

On Parallel $k$-Center Clustering
von: Coy, Sam, et al.
Veröffentlicht: (2023)

Fixed-Parameter Tractability of Hedge Cut
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

The k-Center Problem of Uncertain Points on Graphs
von: Xu, Haitao, et al.
Veröffentlicht: (2025)

Beyond 2-approximation for k-Center in Graphs
von: Jin, Ce, et al.
Veröffentlicht: (2025)

Moderate Dimension Reduction for $k$-Center Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2023)

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers
von: Bousquet, Nicolas, et al.
Veröffentlicht: (2025)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
von: Pilipczuk, Michał, et al.
Veröffentlicht: (2025)

Edge Clique Partition and Cover Beyond Independence
von: Fomin, Fedor V., et al.
Veröffentlicht: (2025)

The Connected k-Vertex One-Center Problem on Graphs
von: Zhang, Jingru
Veröffentlicht: (2024)

Generalized $k$-Center: Distinguishing Doubling and Highway Dimension
von: Feldmann, Andreas Emil, et al.
Veröffentlicht: (2022)

Fixed-Parameter Tractable Submodular Maximization over a Matroid
von: Nematollahi, Shamisa, et al.
Veröffentlicht: (2025)

Hardness, Tractability and Density Thresholds of finite Pinwheel Scheduling Variants
von: Kanellopoulos, Sotiris, et al.
Veröffentlicht: (2026)

Faster Approximation Algorithms for k-Center via Data Reduction
von: Filtser, Arnold, et al.
Veröffentlicht: (2025)

Almost Optimal Fully Dynamic $k$-Center Clustering with Recourse
von: Bhattacharya, Sayan, et al.
Veröffentlicht: (2024)

Structural Parameterizations of $k$-Planarity
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)

Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
von: Holtgrefe, Niels, et al.
Veröffentlicht: (2026)

Binary weights spanning trees and the $k$-red spanning tree problem in linear time
von: Hochbaum, Dorit S.
Veröffentlicht: (2024)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Packing Short Cycles
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
von: Blank, Lotte, et al.
Veröffentlicht: (2025)

On Fixed-Parameter Tractability of Weighted 0-1 Timed Matching Problem on Temporal Graphs
von: Kumar, Rinku, et al.
Veröffentlicht: (2025)

Faster Fixed Parameter Tractable Algorithms for Counting Markov Equivalence Classes with Special Skeletons
von: Sharma, Vidya Sagar
Veröffentlicht: (2023)

Hybrid k-Clustering: Blending k-Median and k-Center
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
von: Arenas, Marcelo, et al.
Veröffentlicht: (2024)

Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
von: Mizutani, Yosuke, et al.
Veröffentlicht: (2024)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
von: Grilnberger, Mara, et al.
Veröffentlicht: (2026)

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
von: Tayal, Mumuksh
Veröffentlicht: (2025)

Tractable Graph Structures in EFX Orientation
von: Blažej, Václav, et al.
Veröffentlicht: (2025)

Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
von: Blauth, Jannis, et al.
Veröffentlicht: (2025)

Optimizing Administrative Divisions: A Vertex $k$-Center Approach for Edge-Weighted Road Graphs
von: Daugulis, Peteris
Veröffentlicht: (2025)

Approximating Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)