An FPT algorithm for splitting a necklace among two thieves

DOI10.1007/S00453-025-01346-4MaRDI QIDQ6894405zbMATH OpenFDO

Authors Michaela Borzechowski, Patrick Schnider, Simon Weber

Publication date 25 November 2025

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00453-025-01346-4

zbMATH Keywords

alpha-ham-sandwich problemfixed-parameter tractabilitynecklace splittingwell-separation

Mathematics Subject Classification ID

Partitions of sets (05A18) Parameterized complexity, tractability and kernelization (68Q27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Nonnumerical algorithms (68W05)

Cites work

• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Bisection of Circle Colorings
• Computational complexity of the -Ham-Sandwich problem
• Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
• Generalized sandwich theorems
• Generalized ham-sandwich cuts
• scientific article; zbMATH DE number 3510345 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
• Maximum cut on line and total graphs
• On some extremal problems in graph theory
• Separations in proof complexity and TFNP
• Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
• Some Extremal Properties of Bipartite Subgraphs
• Splitting necklaces
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• The complexity of splitting necklaces and bisecting ham sandwiches
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• Well-separation and hyperplane transversals in high dimensions

This page was built for publication: An FPT algorithm for splitting a necklace among two thieves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6894405)