On the Complexity of Some Enumeration Problems for Matroids
From MaRDI portal
Publication:5470804
DOI10.1137/S0895480103428338zbMath1104.05017OpenAlexW2086542011MaRDI QIDQ5470804
Kazuhisa Makino, Endre Boros, Vladimir A. Gurvich, Khaled M. Elbassioni, Leonid G. Khachiyan
Publication date: 1 June 2006
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480103428338
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Enumerative combinatorics (05A99)
Related Items
Covering Vectors by Spaces: Regular Matroids, Min‐sum controllable risk problems with concave risk functions of the same value range, On the complexity of enumerating pseudo-intents, Quantum algorithms for learning hidden strings with applications to matroid problems, Invited talks, a-tint: a polymake extension for algorithmic tropical intersection theory, Generating cut conjunctions in graphs and related problems, On the (co)girth of a connected matroid, Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions, On the complexity of monotone dualization and generating minimal hypergraph transversals, Scientific contributions of Leo Khachiyan (a short overview), Trichotomies in the complexity of minimal inference, Algorithmic aspects of Steiner convexity and enumeration of Steiner trees, Computing the spark: mixed-integer programming for the (vector) matroid girth problem, Monadic second-order model-checking on decomposable matroids, Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry, Incremental delay enumeration: space and time, Unnamed Item, Linear codes over signed graphs, Enumerating Vertices of Covering Polyhedra with Totally Unimodular Constraint Matrices, Precision and Sensitivity in Detailed-Balance Reaction Networks, On the complexity of solution extension of optimization problems, Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
