Complexity of testing reachability in matroids

DOI10.4086/CJTCS.2014.005MaRDI QIDQ3191148zbMATH OpenOpenAlexFDO

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

Publication date 24 September 2014

Published in Chicago Journal of Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/cjtcs.2014.005

zbMATH Keywords

matroid theoryreachability problemsspace complexity

Mathematics Subject Classification ID

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

Recommendations

• On the Complexity of Matroid Isomorphism Problems
• On the complexity of matroid isomorphism problem
• Spanning circuits in regular matroids
• On Matroid Representability and Minor Problems
• Matroid Complexity and Nonsuccinct Descriptions

Cites work

• A characterisation of binary transversal structures
• A note on closure properties of logspace MOD classes
• Computational Complexity
• Connectivity in Matroids
• Gammoids and transversal matroids
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 1256731 (Why is no real title available?)
• Inequivalent Representations of Bias Matroids
• Matroid Complexity and Nonsuccinct Descriptions
• Maze recognizing automata and nondeterministic tape complexity
• On the Abstract Properties of Linear Dependence
• Problems complete for deterministic logarithmic space
• Reachability Problems: An Update
• Space-bounded reducibility among combinatorial problems

Cited in

(4)

• Space complexity of reachability testing in labelled graphs
• Matroid Complexity and Nonsuccinct Descriptions
• Space Complexity of Reachability Testing in Labelled Graphs
• On the complexity of matroid isomorphism problem

This page was built for publication: Complexity of testing reachability in matroids

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