Cover Image

A Faster Algorithm for Constrained Correlation Clustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, Nick, Kipouridis, Evangelos, Klausen, Jonas, Thorup, Mikkel
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster algorithms for k-Orthogonal Vectors in low dimension
by: Dürr, Anita, et al.
Published: (2025)

Hashing for Sampling-Based Estimation
by: Aamand, Anders, et al.
Published: (2024)

Combinatorial Correlation Clustering
by: Cohen-Addad, Vincent, et al.
Published: (2024)

A Broader View on Clustering under Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2025)

Clustering to Minimize Cluster-Aware Norm Objectives
by: Herold, Martin G., et al.
Published: (2024)

Instance-Optimality in PageRank Computation
by: Thorup, Mikkel, et al.
Published: (2025)

Connectivity augmentation is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

Faster All-Pairs Optimal Electric Car Routing
by: Dorfman, Dani, et al.
Published: (2025)

Fitting Tree Metrics and Ultrametrics in Data Streams
by: Carmel, Amir, et al.
Published: (2025)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Computing the (k+2)-Edge-Connected Components in k-Edge-Connected Digraphs in Subquadratic Time
by: Georgiadis, Loukas, et al.
Published: (2026)

Static to Dynamic Correlation Clustering
by: Cao, Nairen, et al.
Published: (2025)

Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
by: Jin, Wenyu, et al.
Published: (2024)

Solving the Correlation Cluster LP in Sublinear Time
by: Cao, Nairen, et al.
Published: (2025)

Pivot based correlation clustering in the presence of good clusters
by: Lolck, David Rasmussen, et al.
Published: (2026)

PageRank Centrality in Directed Graphs with Bounded In-Degree
by: Thorup, Mikkel, et al.
Published: (2025)

Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
by: Narayanan, Shyam, et al.
Published: (2024)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

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

Node-Weighted Triangles: Faster and Simpler
by: Akmal, Shyan, et al.
Published: (2026)

Estimating Random-Walk Probabilities in Directed Graphs
by: Bertram, Christian, et al.
Published: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
by: Huang, Shang-En, et al.
Published: (2016)

Fast Similarity Sketching
by: Dahlgaard, Søren, et al.
Published: (2017)

Dynamic data structures for twin-ordered matrices
by: Bosek, Bartłomiej, et al.
Published: (2026)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
by: Goranci, Gramoz, et al.
Published: (2023)

A Simple Algorithm for Trimmed Multipoint Evaluation
by: Fischer, Nick, et al.
Published: (2025)

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

Better coloring of 3-colorable graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2024)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

An FPT Constant-Factor Approximation Algorithm for Correlation Clustering
by: Zhou, Jianqi, et al.
Published: (2025)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
by: Fischer, Nick
Published: (2026)

Sumsets, 3SUM, Subset Sum: Now for Real!
by: Fischer, Nick
Published: (2024)

Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
by: Fischer, Nick, et al.
Published: (2026)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)

Simple Algorithms for Bad Triangle Transversals with Applications to Correlation Clustering
by: Adriaens, Florian, et al.
Published: (2026)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)