Bisection of Circle Colorings

DOI10.1137/0606010MaRDI QIDQ3222851zbMATH OpenOpenAlexWikidataFDO

Authors Charles H. Goldberg, Douglas B. West

Publication date 1985

Published in SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0606010

zbMATH Keywords

bisectioncontinuously integrable functionsnecklaceNP-completenessVLSI circuit design

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Splitting necklaces
• Computing solutions of the paintshop-necklace problem
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• scientific article; zbMATH DE number 496046
• Splitting necklaces and measurable colorings of the real line

Cites work

• scientific article; zbMATH DE number 3562121 (Why is no real title available?)
• scientific article; zbMATH DE number 3232606 (Why is no real title available?)
• Inscribed Squares in Plane Curves
• Quantum private communication
• Some Unsolved Problems in Plane Geometry

Cited in

(38)

• Paintshop, odd cycles and necklace splitting
• Splitting necklaces
• Computing solutions of the paintshop-necklace problem
• Consensus-halving via theorems of Borsuk-Ulam and Tucker
• Cyclic cutwidths of the two-dimensional ordinary and cylindrical meshes
• Equipartition of mass distributions by hyperplanes
• The complexity of finding fair independent sets in cycles
• Two's company, three's a crowd: consensus-halving for a constant number of agents
• Upper bounds for the necklace folding problems
• Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
• Splitting multidimensional necklaces
• Simplotopal maps and necklace splitting
• Measure partitions using hyperplanes with fixed directions
• Discrete geometry on colored point sets in the plane -- a survey
• Obstacles for splitting multidimensional necklaces
• Splitting necklaces and measurable colorings of the real line
• The Chromatic Number of Kneser Hypergraphs
• An approach to emulating separable graphs
• Thieves can make sandwiches
• Fair division and generalizations of Sperner- and KKM-type results
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• Hardness results for consensus-halving
• A survey of mass partitions
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Consensus Halving for Sets of Items
• Consensus-Halving: Does It Ever Get Easier?
• Optimal cache-oblivious mesh layouts
• Words avoiding tangrams
• An FPT algorithm for splitting a necklace among two thieves
• An FPT algorithm for splitting a necklace among two thieves
• Constant inapproximability for PPA
• Size-Ramsey numbers of structurally sparse graphs
• The complexity of finding fair independent sets in cycles
• Efficient splitting of necklaces
• Fair distribution of bundles

This page was built for publication: Bisection of Circle Colorings

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