ORIENTING GRAPHS TO OPTIMIZE REACHABILITY

Citation
Sl. Hakimi et al., ORIENTING GRAPHS TO OPTIMIZE REACHABILITY, Information processing letters, 63(5), 1997, pp. 229-235
Citations number
12
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
ISSN journal
00200190
Volume
63
Issue
5
Year of publication
1997
Pages
229 - 235
Database
ISI
SICI code
0020-0190(1997)63:5<229:OGTOR>2.0.ZU;2-M
Abstract
It is well known that every 2-edge-connected graph can be oriented so that the resulting digraph is strongly connected. Here we study the pr oblem of orienting a connected graph with cut edges in order to maximi ze the number of ordered vertex pairs (x,y) such that there is a direc ted path from x to y. After transforming this problem, we prove a key theorem about the transformed problem that allows us to obtain a quadr atic algorithm for the original orientation problem. We also consider how to orient graphs to minimize the number of ordered vertex pairs jo ined by a directed path. After showing this problem is equivalent to t he comparability graph completion problem, we show both problems are N P-hard, and even NP-hard to approximate to within a factor of 1 + epsi lon, for some epsilon > 0. (C) 1997 Published by Elsevier Science B.V.