Name
Abstract | ||
|---|---|---|
Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. As a consequence, we obtain algorithms which, for a hypergraph H on n vertices and m hyperedges, compute its generalized hypertree-width in time O^@?(2^n) and its fractional hypertree-width in time O(1.734601^n@?m). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.ipl.2011.12.002 | Information Processing Letters |
Keywords | DocType | Volume |
n vertex,fractional hypertree-width,computing hypergraph width,constraint satisfaction problem,time o,hypergraph h,large variety,general exact exponential algorithm,m hyperedges,hypergraph width measure,generalized hypertree-width,computational complexity,data structure,tree decomposition | Journal | 112 |
Issue | ISSN | Citations |
6 | 0020-0190 | 3 |
PageRank | References | Authors |
0.44 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lukas Moll | 1 | 3 | 0.44 |
| Siamak Tazari | 2 | 102 | 6.32 |
| Marc Thurley | 3 | 99 | 6.02 |