Temporalizing digraphs via linear-size balanced bi-trees

Author name not available (Why is that?)

Abstract: In a directed graph

D

on vertex set

v_{1}, d o t s, v_{n}

, a emph{forward arc} is an arc

v_{i} v_{j}

where

i < j

. A pair

v_{i}, v_{j}

is emph{forward connected} if there is a directed path from

v_{i}

to

v_{j}

consisting of forward arcs. In the { t Forward Connected Pairs Problem} ({ t FCPP}), the input is a strongly connected digraph

D

, and the output is the maximum number of forward connected pairs in some vertex enumeration of

D

. We show that { t FCPP} is in APX, as one can efficiently enumerate the vertices of

D

in order to achieve a quadratic number of forward connected pairs. For this, we construct a linear size balanced bi-tree

T

(an out-tree and an in-tree with same size which roots are identified). The existence of such a

T

was left as an open problem motivated by the study of temporal paths in temporal networks. More precisely,

T

can be constructed in quadratic time (in the number of vertices) and has size at least

n / 3

. The algorithm involves a particular depth-first search tree (Left-DFS) of independent interest, and shows that every strongly connected directed graph has a balanced separator which is a circuit. Remarkably, in the request version { t RFCPP} of { t FCPP}, where the input is a strong digraph

D

and a set of requests

R

consisting of pairs

x_{i}, y_{i}

, there is no constant

c > 0

such that one can always find an enumeration realizing

c . | R |

forward connected pairs

x_{i}, y_{i}

(in either direction).

Mathematics Subject Classification ID

No records found.

This page was built for publication: Temporalizing digraphs via linear-size balanced bi-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509570)