Name
Abstract | ||
|---|---|---|
We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a O(log k) approximation algorithm for the treewidth of arbitrary graphs, where k is the treewidth of the input graph. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/S0166-218X(03)00440-2 | Discrete Applied Mathematics |
Keywords | Field | DocType |
asteroidal number,different technique,bounded asteroidal number,graph algorithm,constant factor approximation,natural heuristic,treewidth,approximation algorithm,arbitrary graph,minimal separator,log k,treewidth approximation,input graph | Discrete mathematics,Combinatorics,Tree-depth,Partial k-tree,Tree decomposition,Chordal graph,Clique-sum,Treewidth,Pathwidth,1-planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
136 | 2-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
19 | 0.99 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Bouchitté | 1 | 172 | 12.07 |
| D. Kratsch | 2 | 109 | 7.34 |
| H. Müller | 3 | 19 | 0.99 |
| I. Todinca | 4 | 35 | 2.01 |