The number of unique-sink orientations of the hypercube

DOI10.1007/S00493-006-0007-0MaRDI QIDQ2495697zbMATH OpenOpenAlexFDO

Authors Jiří Matoušek

Publication date 2 January 2007

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-006-0007-0

zbMATH Keywords

optimization problems

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Abstract computational complexity for mathematical programming problems (90C60)

Review text

The author considers the unique-sink orientations of the hypercube which are used as abstract models for many optimization problems. He recalls the total number of orientations of the hypercube and then tries to calculate the number of these orientations. He also gives lower and upper bounds for this number in the case of the \(d\)-dimensional cube. The paper includes a nice historical background on the problem.

Recommendations

• Counting unique-sink orientations
• Mathematical Foundations of Computer Science 2004
• scientific article; zbMATH DE number 1947444
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• Oriented hypercubes

Cited in

(11)

• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Generation of proper families of functions
• Counting unique-sink orientations
• scientific article; zbMATH DE number 1947444 (Why is no real title available?)
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Exponential lower bounds for history-based simplex pivot rules on abstract cubes
• One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes
• On flipping edge sets in unique sink orientations
• On the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• Violator spaces: Structure and algorithms
• Algorithms for media

This page was built for publication: The number of unique-sink orientations of the hypercube

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