@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",

}