On the maximum weight minimal separator

T. Hanaka, H.L. Bodlaender, T.C. van der Zanden, H. Ono

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)

Samenvatting

Given an undirected and connected graph G = (V, E) and two vertices s, t ∈ V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper subset of S separates s and t. In this paper, we consider finding a minimal s-t separator with maximum weight on a vertex-weighted graph. We first prove that this problem is NP-hard. Then, we propose an twO( tw) n-time deterministic algorithm based on tree decompositions. Moreover, we also propose an O (9tw W2)-time randomized algorithm to determine whether there exists a minimal s-t separator where W is its weight and tw is the treewidth of G.

Originele taal-2Engels
TitelTheory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
Plaats van productieCham
UitgeverijSpringer
Pagina's304-318
Aantal pagina's15
ISBN van geprinte versie9783319559100
DOI's
StatusGepubliceerd - 2017
Evenement14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Zwitserland
Duur: 20 apr. 201722 apr. 2017

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10185
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Land/RegioZwitserland
StadBern
Periode20/04/1722/04/17

Vingerafdruk

Duik in de onderzoeksthema's van 'On the maximum weight minimal separator'. Samen vormen ze een unieke vingerafdruk.

Citeer dit