Cover Image

Coloring for dispersion: A polynomial-time algorithm for cardinality-constrained 2-anticlustering

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Tran, Nguyen Khoa, Mu, Lin, Papenberg, Martin, Klau, Gunnar W.
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

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
by: Tan, Jingjing
Published: (2024)

A faster polynomial-space algorithm for Hamiltonian cycle parameterized by treedepth
by: Kratsch, Stefan
Published: (2026)

A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
by: Grigoriev, Alexander, et al.
Published: (2025)

Randomized $k$-server in polynomial time
by: Coester, Christian, et al.
Published: (2026)

Efficient algorithms for computing bisimulations for nondeterministic fuzzy transition systems
by: Nguyen, Linh Anh
Published: (2024)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Canonical forms for matrix tuples in polynomial time
by: Qiao, Youming, et al.
Published: (2024)

On Computing the Dollo-1 phylogeny in polynomial time
by: Bonizzoni, Paola, et al.
Published: (2016)

ExpoSort: Breaking the quasi-polynomial-time barrier for reluctant sorting
by: Abrahamsen, Mikkel
Published: (2024)

Size-constrained Weighted Ancestors with Applications
by: Bille, Philip, et al.
Published: (2023)

A simple linear-time algorithm for generating auxiliary 3-edge-connected subgraphs
by: Tsin, Yung H.
Published: (2023)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Dependent randomized rounding for clustering and partition systems with knapsack constraints
by: Harris, David G., et al.
Published: (2017)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

An $O(n^3)$ time algorithm for the maximum-weight limited-capacity many-to-many matching
by: Rajabi-Alni, Fatemeh, et al.
Published: (2014)

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

On polynomial kernelization for Stable Cutset
by: Kratsch, Stefan, et al.
Published: (2024)

Enumerating all minimal hitting sets in polynomial total time
by: Wild, Marcel
Published: (2023)

A practical algorithm for 3-admissibility
by: Awofeso, Christine, et al.
Published: (2025)

Deterministic Edge Coloring with few Colors in CONGEST
by: Blikstad, Joakim, et al.
Published: (2026)

Coloring 3-Colorable Graphs with Low Threshold Rank
by: Hsieh, Jun-Ting
Published: (2025)

The clustered Sparrow algorithm
by: Dumitrescu, Cristian
Published: (2018)

Factorizing the Brauer monoid in polynomial time
by: Marchei, Daniele, et al.
Published: (2024)

Improved SDP-Based Algorithm for Coloring 3-Colorable Graphs
by: Bansal, Nikhil, et al.
Published: (2026)

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Parameterized algorithms for $k$-Inversion
by: Antony, Dhanyamol, et al.
Published: (2026)

Streaming algorithms for products of probabilities
by: Lohrey, Markus, et al.
Published: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
by: Bhattacharya, Sayan, et al.
Published: (2024)

Solving the List Coloring Problem through a Branch-and-Price algorithm
by: Lucci, Mauro, et al.
Published: (2023)

Parallel Derandomization for Coloring
by: Coy, Sam, et al.
Published: (2023)

Kernelization for $H$-Coloring
by: Berkman, Yael, et al.
Published: (2025)

A customizable inexact subgraph matching algorithm for attributed graphs
by: Benko, Tatyana, et al.
Published: (2025)

A computational study of Gomory-Hu construction tree algorithms
by: Kolmogorov, Vladimir
Published: (2022)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

Engineering Semi-streaming DFS algorithms
by: Bhagavan, Kancharla Nikhilesh, et al.
Published: (2024)

Insights into $(k,ρ)$-shortcutting algorithms
by: Leonhardt, Alexander, et al.
Published: (2024)

New algorithms for girth and cycle detection
by: Roditty, Liam, et al.
Published: (2025)

Practical algorithms for Hierarchical overlap graphs
by: Talera, Saumya, et al.
Published: (2024)

A Near-Optimal Kernel for a Coloring Problem
by: Haviv, Ishay, et al.
Published: (2025)