Complexity of existence of m-cycle in planar graph with n nodes
G is a planar graph with n nodes.
What are the complexity of following problems?- A: Does G contain a m-cycle? (m开发者_开发问答-cycle is a simple cycle with m nodes, m
- B: complexity of counting all m-cycles in G.
- what is the complexity of A and B if G is an arbitrary given graph?
Pointing to books and papers is also useful...
精彩评论