The Complexity of Counting Eulerian Tours in?4-regular Graphs |
| |
| Authors: | Qi Ge Daniel ?tefankovi? |
| |
| Affiliation: | 1. Department of Computer Science, University of Rochester, NY, 14627, Rochester, USA
|
| |
| Abstract: | We investigate the complexity of counting Eulerian tours (#ET) and its variations from two perspectives—the complexity of exact counting and the complexity w.r.t. approximation-preserving
reductions (AP-reductions, Dyer et al., Algorithmica 38(3):471–500, 2004). We prove that #ET is #P-complete even for planar 4-regular graphs. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
