Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs |
| |
Authors: | Jiong Guo,Falk Hü ffner,Erhan Kenar,Rolf Niedermeier,Johannes Uhlmann |
| |
Affiliation: | 1. Institut für Informatik, Friedrich-Schiller-Universität Jena, Ernst-Abbe-Platz 2, D-07743 Jena, Germany;2. Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany |
| |
Abstract: | Multicut is a fundamental network communication and connectivity problem. It is defined as: given an undirected graph and a collection of pairs of terminal vertices, find a minimum set of edges or vertices whose removal disconnects each pair. We mainly focus on the case of removing vertices, where we distinguish between allowing or disallowing the removal of terminal vertices. Complementing and refining previous results from the literature, we provide several NP-completeness and (fixed-parameter) tractability results for restricted classes of graphs such as trees, interval graphs, and graphs of bounded treewidth. |
| |
Keywords: | Combinatorial optimization Complexity theory NP-completeness Dynamic programming Graph theory Parameterized complexity |
本文献已被 ScienceDirect 等数据库收录! |
|