@inproceedings{c2d36dcb58574633a691638d889c17b9,
title = "Separators are as simple as cutsets",
abstract = "We show that all minimal a-b separators (vertex sets) dis- connecting a pair of given non-adjacent vertices a and b in an undirected and connected graph with n vertices can be computed in O(n2Rab) time, where Rab is the number of minimal a-b separators. This result matches the known worst-case time complexity of its counterpart problem of com- puting all a-b cutsets (edge sets) [13] and solves an open problem posed in [11].",
keywords = "Algorithms, Complexity analysis, Cutsets, Data structures, Separators",
author = "Hong Shen and Keqin Li and Zheng, \{Si Qing\}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 5th Asian Computing Science Conference on Advances in Computing Science, ASIAN 1999 ; Conference date: 10-12-1999 Through 12-12-1999",
year = "1999",
doi = "10.1007/3-540-46674-6\_29",
language = "English",
isbn = "354066856X",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "347--358",
editor = "Roland Yap and P.S. Thiagarajan",
booktitle = "Advances in Computing Science - ASIAN 1999 - 5th Asian Computing Science Conference, Proceedings",
address = "Germany",
}