On the complexity of matroid isomorphism problem

DOI10.1007/s00224-010-9260-0zbMath1230.68115arXiv0811.3859OpenAlexW2080471023MaRDI QIDQ639843

B. V. Raghavendra Rao, M. N. Jayalal Sarma

Publication date: 11 October 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0811.3859

zbMATH Keywords

computational complexitymatroid isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matroids and geometric lattices (05B35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

Isomorphism testing of read-once functions and polynomials ⋮ On the Complexity of Matroid Isomorphism Problems ⋮ TESTING MUTUAL DUALITY OF PLANAR GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Vector representable matroids of given rank with given automorphism group
• Probabilistic complexity classes and lowness
• Some hard problems on matroid spikes
• Graph Isomorphism is in SPP
• Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• 3-connected Planar Graph Isomorphism is in Log-space
• Matroid Complexity and Nonsuccinct Descriptions
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• A Combinatorial Decomposition Theory
• On Whitney's 2‐isomorphism theorem for graphs
• On the Abstract Properties of Linear Dependence
• Dividing a Graph into Triconnected Components
• Computational Complexity

This page was built for publication: On the complexity of matroid isomorphism problem