On the Complexity of Matroid Isomorphism Problems

DOI10.1007/978-3-642-03351-3_27MaRDI QIDQ3392964zbMATH OpenOpenAlexFDO

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

Publication date 18 August 2009

Published in Computer Science - Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03351-3_27

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of matroid isomorphism problem
• The complexity of the matroid homomorphism problem
• On the Complexity of Some Enumeration Problems for Matroids
• On the complexity of polytope isomorphism problems
• On the number of non-isomorphic matroids
• scientific article; zbMATH DE number 477971
• Query complexity of matroids
• scientific article; zbMATH DE number 512806
• The computational complexity of equivalence and isomorphism problems
• Matroid Complexity and Nonsuccinct Descriptions

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 5605063 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• 2-Isomorphic Graphs
• 3-connected Planar Graph Isomorphism is in Log-space
• A Combinatorial Decomposition Theory
• A Polynomial-Time Algorithm to Find the Shortest Cycle Basis of a Graph
• Chromatic, Flow and Reliability Polynomials: The Complexity of their Coefficients
• Completeness results for graph isomorphism.
• Computational Complexity
• Dividing a Graph into Triconnected Components
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Logical Approaches to Computational Barriers
• Matroid Complexity and Nonsuccinct Descriptions
• On Whitney's 2‐isomorphism theorem for graphs
• On the Hardness of Graph Isomorphism
• On the complexity of matroid isomorphism problem
• Some hard problems on matroid spikes
• Vector representable matroids of given rank with given automorphism group

Cited in

(9)

• The complexity of deletion problems for matroids
• On the Complexity of Some Enumeration Problems for Matroids
• On the complexity of polytope isomorphism problems
• The complexity of the matroid homomorphism problem
• Matroid Complexity and Nonsuccinct Descriptions
• On the complexity of matroid isomorphism problem
• Computation of lattice isomorphisms and the integral matrix similarity problem
• Complexity of testing reachability in matroids
• Determining when a graphic matroid is transversal in linear time

This page was built for publication: On the Complexity of Matroid Isomorphism Problems

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