Name
Abstract | ||
|---|---|---|
We present a bound of $m/5.769+O(\log n)$ on the pathwidth of graphs with $m$ edges. Respective path decompositions can be computed in polynomial time. Using a well-known framework for algorithms that rely on tree decompositions, this directly leads to runtime bounds of $O^*(2^{m/5.769})$ for Max-2SAT and Max-Cut. Both algorithms require exponential space due to dynamic programming. If we agree to accept a slightly larger bound of $m/5.217+3$, we even obtain path decompositions with a rather simple structure: all bags share a large set of common nodes. Using branching based algorithms, this allows us to solve the same problems in polynomial space and time $O^*(2^{m/5.217})$. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/080715482 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
common node,path decomposition,large set,exact algorithms,respective path decomposition,polynomial space,polynomial time,dynamic programming,simple structure,log n,exponential space,sparse graphs,algorithms,graph theory | Graph theory,Space time,Binary logarithm,Discrete mathematics,Combinatorics,Exponential function,Algorithm,Decomposition method (constraint satisfaction),PSPACE,Time complexity,Pathwidth,Mathematics | Journal |
Volume | Issue | ISSN |
23 | 1 | 0895-4801 |
Citations | PageRank | References |
11 | 0.52 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joachim Kneis | 1 | 271 | 16.14 |
| Daniel Mölle | 2 | 175 | 10.17 |
| Stefan Richter | 3 | 176 | 9.96 |
| Peter Rossmanith | 4 | 1000 | 61.03 |