Traversing combinatorial 0/1-polytopes via optimization
type: Item
instance of: scholarly article
title: Traversing combinatorial 0/1-polytopes via optimization
author: Arturo I. Merino
author: Torsten Mütze
published in: SIAM Journal on Computing
publication date: 2024-09-11T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 52B05
Mathematics Subject Classification ID: 52B11
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 7910862
zbMATH Keywords: generation
zbMATH Keywords: 0/1-polytope
zbMATH Keywords: Hamilton path
zbMATH Keywords: Gray code
zbMATH Keywords: vertex enumeration
MaRDI profile type: MaRDI publication profile
cites work: Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
cites work: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
cites work: Reverse search for enumeration
cites work: Q4518988
cites work: 0/1 vertex and facet enumeration with BDDs
cites work: Q3622253
cites work: The negative cycles polyhedron and hardness of checking some polyhedral properties
cites work: The vertex set of a \(0/1\)-polytope is strongly \(\mathcal P\)-enumerable
cites work: Q4371290
cites work: Proximity Search for Maximal Subgraph Enumeration
cites work: A pivot Gray code listing for the spanning trees of the fan graph
cites work: A minimum spanning tree algorithm with inverse-Ackermann type complexity
cites work: On-line and off-line vertex enumeration by adjacency lists
cites work: On certain polytopes associated with graphs
cites work: A Hamilton cycle in the \(k\)-sided pancake network
cites work: Scaling Algorithms for Weighted Matching in General Graphs
cites work: Q5743486
cites work: The Complexity of Vertex Enumeration Methods
cites work: Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices
cites work: Finding all minimum-cost perfect matchings in Bipartite graphs
cites work: Recognition algorithms for orders of small width and graphs of small Dilworth number
cites work: A Data Structure for Nearest Common Ancestors with Linking
cites work: Maximum weight independent sets and cliques in intersection graphs of filaments
cites work: Combinatorial generation via permutation languages. I. Fundamentals
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Q3858023
cites work: Efficient algorithms on distributive lattices
cites work: Q2957449
cites work: Q4037441
cites work: Combinatorial optimization. Theory and algorithms
cites work: On Rotations and the Generation of Binary Trees
cites work: All your bases are belong to us: listing all bases of a matroid by greedy exchanges
cites work: A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets
cites work: Q5817857
cites work: Combinatorial Gray codes -- an updated survey
cites work: Hamiltonicity and combinatorial polyhedra
cites work: Hamiltonicity in (0-1)-polyhedra
cites work: Max flows in O(nm) time, or better
cites work: Gray codes from antimatroids
cites work: Binary bubble languages and cool-lex order
cites work: Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
cites work: A Survey of Combinatorial Gray Codes
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: Two poset polytopes
cites work: Efficient oracles for generating binary bubble languages
cites work: Greedy flipping of pancakes and burnt pancakes
cites work: Integer priority queues with decrease key in constant time and the single source shortest paths problem
cites work: Q4370201
cites work: Q4938674
cites work: Q4452089
cites work: The Greedy Gray Code Algorithm
cites work: Listing all the minimum spanning trees in an undirected graph
cites work: A new algorithm for generation of permutations
cites work: Lectures on Polytopes
DOI: 10.1137/23M1612019
description: scientific article; zbMATH DE number 7910862