On orientations maximizing total arc-connectivity

Abstract: For a given digraph

D

and distinct

u, v i n V (D)

, we denote by

l a m b d a_{D} (u, v)

the local arc-connectivity from

u

to

v

. Further, we define the total arc connectivity

t a c (D)

of

D

to be

s u m_{u, v s u b s e t e q V (D)} l a m b d a_{D} (u, v) + l a m b d a_{D} (v, u)

. We show that, given a graph

G

and an integer

k

, it is NP-complete to decide whether

G

has an orientation

v e c G

satisfying

t a c (v e c G) g e q k

. This answers a question of Pekec. On the positive side, we show that the corresponding maximization problem admits a

f r a c 23

-approximation algorithm.

Cites work

Cited in

(3)

This page was built for publication: On orientations maximizing total arc-connectivity