Report
Counting Cycles on Planar Graphs in Subexponential Time
| العنوان: | Counting Cycles on Planar Graphs in Subexponential Time |
|---|---|
| المؤلفون: | Cai, Jin-Yi, Maran, Ashwin |
| سنة النشر: | 2022 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Data Structures and Algorithms, Mathematics - Combinatorics |
| الوصف: | We study the problem of counting all cycles or self-avoiding walks (SAWs) on triangulated planar graphs. We present a subexponential $2^{O(\sqrt{n})}$ time algorithm for this counting problem. Among the technical ingredients used in this algorithm are the planar separator theorem and a delicate analysis using pairs of Motzkin paths and Motzkin numbers. We can then adapt this algorithm to uniformly sample SAWs, in subexponential time. Our work is motivated by the problem of gerrymandered districting maps. Comment: 28 pages, 6 figures, COCOON 2022 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2208.09948 |
| رقم الانضمام: | edsarx.2208.09948 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |