On the efficiency of representability tests for matroids

DOI10.1016/S0195-6698(82)80039-5zbMath0505.05021MaRDI QIDQ1835922

Klaus Truemper

Publication date: 1982

Published in: European Journal of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

binary matroid; polynomial time algorithms; graphic matroid; matroid representation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05B35: Combinatorial aspects of matroids and geometric lattices

Related Items

A decomposition theory for matroids. I: General results, A decomposition theory for matroids. II. Minimal violation matroids, A decomposition theory for matroids. III. Decomposition conditions, A decomposition theory for matroids. V: Testing of matrix total unimodularity, On the classification of ideal secret sharing schemes, A decomposition theory for matroids. VII: Analysis of minimal violation matrices, On the efficiency of representability tests for matroids, Partial matroid representations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An efficient PQ-graph algorithm for solving the graph-realization problem
• Decomposition of regular matroids
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Recognizing graphic matroids
• The dependence graph for bases in matroids
• On the efficiency of representability tests for matroids
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• The computational complexity of matroid properties
• Converting Linear Programs to Network Problems
• Functions of Bounded Second Variation and Stieltjes-Type Integrals
• On Whitney's 2‐isomorphism theorem for graphs
• Lectures on matroids