Orienting Graphs to Optimize Reachability

Details Orienting Graphs to Optimize Reachability Orienting Graphs to Optimize Reachability

2002-05-18

arxiv.org/abs/cs/0205042v1

Information Processing Letters 63:229-235 (1997)

Computer Science

Data Structures and Algorithms

Scientific paper

The paper focuses on two problems: (i) how to orient the edges of an undirected graph in order to maximize the number of ordered vertex pairs (x,y) such that there is a directed path from x to y, and (ii) how to orient the edges so as to minimize the number of such pairs. The paper describes a quadratic-time algorithm for the first problem, and a proof that the second problem is NP-hard to approximate within some constant 1+epsilon > 1. The latter proof also shows that the second problem is equivalent to ``comparability graph completion''; neither problem was previously known to be NP-hard.

Affiliated with

Also associated with

No associations

Rating

Orienting Graphs to Optimize Reachability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Orienting Graphs to Optimize Reachability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Orienting Graphs to Optimize Reachability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-599166