Making Bidirected Graphs Strongly Connected
Tatsuya Matsuoka, Shun Sato · arXiv (Cornell University) · 2017
We consider problems to make a given bidirected graph strongly connected with minimum cardinality of additional signs or additional arcs. For the former problem, we show the minimum number of additional signs and give a linear-time algorithm for finding an optimal solution. For the latter problem, we give a linear-time algorithm for finding a feasible solution whose size is equal to the obvious lower bound or more than that by one.