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

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

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

(10)

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

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)