Name
Abstract | ||
|---|---|---|
A graph $G$ has tree-width at most $k$ if the vertices of $G$ can be decomposed into a tree-like structure of sets of vertices, each set having cardinality at most $k+1$. An alternate definition of tree-width is stated in terms of a $k$-elimination sequence, which is an order to eliminate the vertices of the graph such that each vertex, at the time it is eliminated from the graph, has degree at most $k$. Arnborg and Proskurowski showed that if a graph has tree-width at most a fixed $k$, then many NP-hard problems can be solved in linear time, provided this $k$-elimination sequence is part of the input. These algorithms are very efficient for small $k$, such as 2, 3, or 4, but may be impractical for large $k$ as they depend exponentially on $k$. A reduction process is developed, and reductions are shown that can be applied to a graph of tree-width at most four without increasing its tree-width. Further, each graph of tree-width at most four contains one of these reductions. The reductions are then used in a linear-time algorithm that generates a 4-elimination sequence, if one exists. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1137/S0895480193243043 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
elimination sequence,reduction process,linear-time algorithm,linear recognition,linear time,np-hard problem,tree-like structure,4-elimination sequence,alternate definition,tree width | Discrete mathematics,Combinatorics,Path (graph theory),Graph power,Cycle graph,Regular graph,Null graph,Distance-regular graph,Mathematics,Path graph,Complement graph | Journal |
Volume | Issue | ISSN |
9 | 1 | 0895-4801 |
Citations | PageRank | References |
26 | 1.68 | 1 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel P. Sanders | 1 | 471 | 45.56 |