Algorithms for Cut Problems on Trees

Iyad Kanj; Guohui Lin; Tian Liu; Weitian Tong; G. Xia; Jinhui Xu; Boting Yang; Fenghui Zhang; Peng Zhang; Binhai Zhu

doi:10.1007/978-3-319-12691-3_22

Algorithms for Cut Problems on Trees

Iyad Kanj, Guohui Lin, Tian Liu, Weitian Tong, G. Xia, Jinhui Xu, Boting Yang, Fenghui Zhang, Peng Zhang, Binhai Zhu

Computer Science

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

We study the multicut on trees and the generalized multiway cut on trees problems. For the multicut on trees problem, we present a parameterized algorithm that runs in time O^∗ (ρ^k), where ρ = _ √ 2 + 1 ≈ 1.555 is the positive root of the polynomial x⁴ - 2^x2 - 1. This improves the current-best algorithm of Chen et al. that runs in time O^∗ (1.619^k). By reducing generalized multiway cut on trees to multicut on trees, our results give a parameterized algorithm that solves the generalized multiway cut on trees problem in time O^∗ (ρ^k). We also show that the generalized multiway cut on trees problem is solvable in polynomial time if the number of terminal sets is a fixed constant.

Original language	English
Pages (from-to)	283-298
Number of pages	16
Journal	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8881
DOIs	https://doi.org/10.1007/978-3-319-12691-3_22
State	Published - 2014

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-12691-3_22

Cite this

@article{a9388a7ec6e24201b69aa72f58aa5775,

title = "Algorithms for Cut Problems on Trees",

abstract = "We study the multicut on trees and the generalized multiway cut on trees problems. For the multicut on trees problem, we present a parameterized algorithm that runs in time O∗ (ρk), where ρ = \_ √ 2 + 1 ≈ 1.555 is the positive root of the polynomial x4 - 2x2 - 1. This improves the current-best algorithm of Chen et al. that runs in time O∗ (1.619k). By reducing generalized multiway cut on trees to multicut on trees, our results give a parameterized algorithm that solves the generalized multiway cut on trees problem in time O∗ (ρk). We also show that the generalized multiway cut on trees problem is solvable in polynomial time if the number of terminal sets is a fixed constant.",

author = "Iyad Kanj and Guohui Lin and Tian Liu and Weitian Tong and G. Xia and Jinhui Xu and Boting Yang and Fenghui Zhang and Peng Zhang and Binhai Zhu",

note = "Publisher Copyright: Springer International Publishing Switzerland 2014.",

year = "2014",

doi = "10.1007/978-3-319-12691-3\_22",

language = "English",

volume = "8881",

pages = "283--298",

journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

issn = "0302-9743",

publisher = "Springer Science and Business Media Deutschland GmbH",

}

TY - JOUR

T1 - Algorithms for Cut Problems on Trees

AU - Kanj, Iyad

AU - Lin, Guohui

AU - Liu, Tian

AU - Tong, Weitian

AU - Xia, G.

AU - Xu, Jinhui

AU - Yang, Boting

AU - Zhang, Fenghui

AU - Zhang, Peng

AU - Zhu, Binhai

N1 - Publisher Copyright: Springer International Publishing Switzerland 2014.

PY - 2014

Y1 - 2014

N2 - We study the multicut on trees and the generalized multiway cut on trees problems. For the multicut on trees problem, we present a parameterized algorithm that runs in time O∗ (ρk), where ρ = _ √ 2 + 1 ≈ 1.555 is the positive root of the polynomial x4 - 2x2 - 1. This improves the current-best algorithm of Chen et al. that runs in time O∗ (1.619k). By reducing generalized multiway cut on trees to multicut on trees, our results give a parameterized algorithm that solves the generalized multiway cut on trees problem in time O∗ (ρk). We also show that the generalized multiway cut on trees problem is solvable in polynomial time if the number of terminal sets is a fixed constant.

AB - We study the multicut on trees and the generalized multiway cut on trees problems. For the multicut on trees problem, we present a parameterized algorithm that runs in time O∗ (ρk), where ρ = _ √ 2 + 1 ≈ 1.555 is the positive root of the polynomial x4 - 2x2 - 1. This improves the current-best algorithm of Chen et al. that runs in time O∗ (1.619k). By reducing generalized multiway cut on trees to multicut on trees, our results give a parameterized algorithm that solves the generalized multiway cut on trees problem in time O∗ (ρk). We also show that the generalized multiway cut on trees problem is solvable in polynomial time if the number of terminal sets is a fixed constant.

UR - https://www.scopus.com/pages/publications/84921496753

U2 - 10.1007/978-3-319-12691-3_22

DO - 10.1007/978-3-319-12691-3_22

M3 - Article

AN - SCOPUS:84921496753

SN - 0302-9743

VL - 8881

SP - 283

EP - 298

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -

Algorithms for Cut Problems on Trees

Abstract

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this