The number of unique-sink orientations of the hypercube

DOI10.1007/S00493-006-0007-0zbMATH Open1106.05048OpenAlexW2040434620MaRDI QIDQ2495697FDOQ2495697

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

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

zbMATH Keywords

optimization problems

Mathematics Subject Classification ID

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

Cited In (10)

• Title not available (Why is that?)
• Counting unique-sink orientations
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
• Violator spaces: Structure and algorithms
• Generation of proper families of functions
• Title not available (Why is that?)
• 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 the existence of Hamiltonian paths for history based pivot rules on acyclic unique sink orientations of hypercubes
• 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)