An Improved Algorithm for the Node-to-Set Disjoint Paths Problem on Bi-Rotator Graphs

摘要

Given a source node and a node set, the node-to-set disjoint paths problem is to find disjoint paths from the source node to all nodes from the node set. In this paper, we propose an improved algorithm for the node-to-set disjoint paths problem on bi-rotator graphs. Our result improves the complexity of previous result from O(n~5) to O(n~3 log n), where n is the dimension of the input graph.