Skip to main content
added 15 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This answer might be slightly overkill (and possibly underkill), but here goes. For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, and if so to construct a tree-decomposition of $G$ of width at most $k$. This was proven by Bodlaender in this paper. Note that series-parallel graphs have tree-width at most 2. Therefore, using the above algorithm of Bodlaender, for any series-parallel graph $G$, we can compute a tree-decomposition of $G$ of width at most 2 in linear-time. This tree-decomposition is not exactly what you are looking for (hence the underkill part of the answer), but I think that you may be able to recover your "decomposition tree" from it (although I haven't thought about this carefully).

This answer might be slightly overkill (and possibly underkill), but here goes. For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, and if so to construct a tree-decomposition of $G$ of width at most $k$. This was proven by Bodlaender in this paper. Note that series-parallel graphs have tree-width at most 2. Therefore, using the above algorithm of Bodlaender, for any series-parallel graph $G$, we can compute a tree-decomposition of $G$ of width at most 2. This tree-decomposition is not exactly what you are looking for (hence the underkill part of the answer), but I think that you may be able to recover your "decomposition tree" from it (although I haven't thought about this carefully).

This answer might be slightly overkill (and possibly underkill), but here goes. For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, and if so to construct a tree-decomposition of $G$ of width at most $k$. This was proven by Bodlaender in this paper. Note that series-parallel graphs have tree-width at most 2. Therefore, using the above algorithm of Bodlaender, for any series-parallel graph $G$, we can compute a tree-decomposition of $G$ of width at most 2 in linear-time. This tree-decomposition is not exactly what you are looking for (hence the underkill part of the answer), but I think that you may be able to recover your "decomposition tree" from it (although I haven't thought about this carefully).

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

This answer might be slightly overkill (and possibly underkill), but here goes. For any fixed constant $k$, there is a linear-time algorithm to recognize if a graph $G$ has tree-width at most $k$, and if so to construct a tree-decomposition of $G$ of width at most $k$. This was proven by Bodlaender in this paper. Note that series-parallel graphs have tree-width at most 2. Therefore, using the above algorithm of Bodlaender, for any series-parallel graph $G$, we can compute a tree-decomposition of $G$ of width at most 2. This tree-decomposition is not exactly what you are looking for (hence the underkill part of the answer), but I think that you may be able to recover your "decomposition tree" from it (although I haven't thought about this carefully).