## Abstract

Some new ideas are presented on graph reduction applied to graphs with bounded treewidth. It is shown that the method can not only be applied to solve decision problems, but also some optimization problems and construction variants of several of these problems on graphs with some constant upper bound on the treewidth.

Also, the existence is shown of finite, safe, complete, and terminating sets of reduction rules, such that on any graph G with treewidth at most some constant k, Ω(n) applications of reduction rules can be applied simultaneously. This result is used to obtain a class of randomized parallel algorithms that solve many problems on graphs with bounded treewidth and bounded degree in O(log n) expected time with O(n) processors on a EREW PRAM. Among others, such an algorithm is obtained to recognize the class of graphs with treewidth at most k and maximum vertex degree at most d, for constant k and d.

Also, the existence is shown of finite, safe, complete, and terminating sets of reduction rules, such that on any graph G with treewidth at most some constant k, Ω(n) applications of reduction rules can be applied simultaneously. This result is used to obtain a class of randomized parallel algorithms that solve many problems on graphs with bounded treewidth and bounded degree in O(log n) expected time with O(n) processors on a EREW PRAM. Among others, such an algorithm is obtained to recognize the class of graphs with treewidth at most k and maximum vertex degree at most d, for constant k and d.

Original language | English |
---|---|

Title of host publication | Graph-Theoretic Concepts in Computer Science |

Subtitle of host publication | 19th International Workshop, WG '93 Utrecht, The Netherlands, June 16–18, 1993 Proceedings |

Editors | Jan van Leeuwen |

Publisher | Springer |

Pages | 45-56 |

Number of pages | 12 |

Volume | 790 |

ISBN (Electronic) | 978-3-540-48385-4 |

ISBN (Print) | 978-3-540-57899-4 |

DOIs | |

Publication status | Published - 1994 |

### Publication series

Name | Lecture Notes in Computer Science |
---|