Cover Image

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bai, Tian, Fomin, Fedor V., Golovach, Petr A., More, Yash Hiren, Wietheger, Simon
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization
by: Fomin, Fedor V., et al.
Published: (2025)

Parameterized Complexity of Efficient Sortation
by: Ganian, Robert, et al.
Published: (2024)

Algorithmic Extensions of Dirac's Theorem
by: Fomin, Fedor V., et al.
Published: (2020)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, et al.
Published: (2025)

Matrix Editing Meets Fair Clustering: Parameterized Algorithms and Complexity
by: Ganian, Robert, et al.
Published: (2025)

Parameterized Complexity of Vehicle Routing
by: Döring, Michelle, et al.
Published: (2025)

On the Parameterized Complexity of Odd Coloring
by: Bhyravarapu, Sriram, et al.
Published: (2025)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

Bandwidth Parameterized by Cluster Vertex Deletion Number
by: Gima, Tatsuya, et al.
Published: (2023)

Parameterized Algorithms for Editing to Uniform Cluster Graph
by: Gaikwad, Ajinkya, et al.
Published: (2024)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

When does FTP become FPT?
by: Bentert, Matthias, et al.
Published: (2025)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
by: Frei, Fabian, et al.
Published: (2025)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
by: Bodlaender, Hans L., et al.
Published: (2026)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

Explicit Good Codes Approaching Distance 1 in Ulam Metric
by: Goldenberg, Elazar, et al.
Published: (2024)

H-Planarity and Parametric Extensions: when Modulators Act Globally
by: Fomin, Fedor V., et al.
Published: (2025)

Parameterized Complexity of Finding a Maximum Common Vertex Subgraph Without Isolated Vertices
by: Dey, Palash, et al.
Published: (2026)

Improved Algorithm for Permutation Testing
by: Zhang, Xiaojin
Published: (2020)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

Sampling Permutations with Cell Probes is Hard
by: Alekseev, Yaroslav, et al.
Published: (2025)

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

Parameterized complexity of reconfiguration of atoms
by: Cooper, Alexandre, et al.
Published: (2021)

Parameterized Restless Temporal Path
by: Cauvi, Justine, et al.
Published: (2025)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
by: Fomin, Fedor V., et al.
Published: (2026)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

The Parameterized Landscape of Labeled Graph Contractions
by: Lafond, Manuel, et al.
Published: (2025)

Structural Parameterizations for Induced and Acyclic Matching
by: Lampis, Michael, et al.
Published: (2025)

Parameterized Maximum Node-Disjoint Paths
by: Lampis, Michael, et al.
Published: (2024)

Parameterized Critical Node Cut Revisited
by: Knop, Dušan, et al.
Published: (2025)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

Parameterized Max Min Feedback Vertex Set
by: Lampis, Michael, et al.
Published: (2023)