Space-efficient counting in graphs on surfaces

DOI10.1007/S00037-009-0266-4MaRDI QIDQ626667zbMATH OpenOpenAlexFDO

Authors Mark Braverman, Raghav Kulkarni, Sambuddha Roy

Publication date 18 February 2011

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00037-009-0266-4

zbMATH Keywords

countingnumber of spanning treesplanar graphsproblem complexity

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Relations of low-dimensional topology with graph theory (57M15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Space complexity of perfect matching in bounded genus bipartite graphs
• Space complexity of perfect matching in bounded genus bipartite graphs
• Planarity, determinants, permanents, and (unique) matchings
• Planarity, Determinants, Permanents, and (Unique) Matchings
• Counting trees in a graph is \(\# \text{P}\)-complete

Cited in

(6)

• Space complexity of perfect matching in bounded genus bipartite graphs
• Space complexity of perfect matching in bounded genus bipartite graphs
• Planarity, determinants, permanents, and (unique) matchings
• Planarity, Determinants, Permanents, and (Unique) Matchings
• Spanning trees of 3-uniform hypergraphs
• Universality and asymptotics of graph counting problems in non-orientable surfaces

This page was built for publication: Space-efficient counting in graphs on surfaces

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