On the Complexity of Some Enumeration Problems for Matroids

DOI10.1137/S0895480103428338zbMATH Open1104.05017OpenAlexW2086542011MaRDI QIDQ5470804FDOQ5470804

Authors: Endre Boros, Kazuhisa Makino, Leonid G. Khachiyan, Khaled Elbassioni, Vladimir Gurvich

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

Recommendations

The complexity of the matroid homomorphism problem
On the Complexity of Matroid Isomorphism Problems
On the number of matroids
On the number of matroids
Algorithms and Computation
Enumerating matroids of fixed rank
On the complexity of matroid isomorphism problem
On the generalization of the matroid parity problem
scientific article; zbMATH DE number 3370358
Some problems on approximate counting in graphs and matroids

zbMATH Keywords

circuit hypergraph Steiner tree hyperplane base flat multiway cut incremental polynomial time

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35)

Cited In (46)

Incremental delay enumeration: space and time
Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
The complexity of deletion problems for matroids
On the complexity of solution extension of optimization problems
The generalized column incidence graph and a matroid base-listing algorithm
Title not available (Why is that?)
On the complexity of monotone dualization and generating minimal hypergraph transversals
Some hard problems on matroid spikes
Linear codes over signed graphs
Trichotomies in the complexity of minimal inference
Matroid Steiner problems, the Tutte polynomial and network reliability
Enumerating vertices of \(0/1\)-polyhedra associated with \(0/1\)-totally unimodular matrices
On enumerating minimal dicuts and strongly connected subgraphs
Monadic second-order model-checking on decomposable matroids
Computing the spark: mixed-integer programming for the (vector) matroid girth problem
Precision and sensitivity in detailed-balance reaction networks
Output-sensitive algorithm for generating the flats of a matroid
A combinatorial search problem on matroids
Title not available (Why is that?)
Min‐sum controllable risk problems with concave risk functions of the same value range
Matroid Complexity and Nonsuccinct Descriptions
Title not available (Why is that?)
Enumerating vertices of covering polyhedra with totally unimodular constraint matrices
Combinatorial and geometric approaches to counting problems on linear matroids, graphic arrangements, and partial orders
a-tint: a polymake extension for algorithmic tropical intersection theory
An inequality for polymatroid functions and its applications.
On the Complexity of Matroid Isomorphism Problems
Quantum algorithms for learning hidden strings with applications to matroid problems
Hardness and approximation of submodular minimum linear ordering problems
Generating cut conjunctions in graphs and related problems
ENUMERATING SPANNING AND CONNECTED SUBSETS IN GRAPHS AND MATROIDS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
Title not available (Why is that?)
Polynomial-delay enumeration of large maximal common independent sets in two matroids
Covering Vectors by Spaces: Regular Matroids
Algorithms and Computation
New theoretical results on the monotone Boolean duality and the monotone Boolean dualization problems
Title not available (Why is that?)
Polynomial-delay enumeration algorithms in set systems
Enumerating Spanning and Connected Subsets in Graphs and Matroids
Invited talks
Algorithmic aspects of Steiner convexity and enumeration of Steiner trees
On the complexity of enumerating pseudo-intents
On the (co)girth of a connected matroid
Jump number problem: The role of matroids
Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions
Scientific contributions of Leo Khachiyan (a short overview)

This page was built for publication: On the Complexity of Some Enumeration Problems for Matroids

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