2024-03-28T17:24:11Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002037362023-04-27T10:00:04Z01164:02592:10084:10172
Efficient enumeration of minimal multiway cutsEfficient enumeration of minimal multiway cutsenghttp://id.nii.ac.jp/1001/00203641/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=203736&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Information Processing Society of JapanHokkaido UniversityKyoto UniversityKazuhiro, KuritaYasuaki, KobayashiLet G = (V, E) be an undirected graph and let T ⊆ V be the set of terminals. A multiway cut of (G, T) is a set of edges M ⊆ E that leaves each of terminals in a separate component, that is there is no path between any pair of vertices of T in G' = (V, E\M). In this paper, we give an efficient algorithm for enumerating inclusion-wise minimal multiway cuts of (G, T) in O(Let G = (V, E) be an undirected graph and let T ⊆ V be the set of terminals. A multiway cut of (G, T) is a set of edges M ⊆ E that leaves each of terminals in a separate component, that is there is no path between any pair of vertices of T in G' = (V, E\M). In this paper, we give an efficient algorithm for enumerating inclusion-wise minimal multiway cuts of (G, T) in O(AN1009593X研究報告アルゴリズム(AL)2020-AL-1776152020-03-092188-85662020-02-27