A note on orientations of mixed graphs

A note on orientations of mixed graphs,10.1016/S0166-218X(01)00228-1,Discrete Applied Mathematics,Esther M. Arkin,Refael Hassin

A note on orientations of mixed graphs   (Citations: 4)
BibTex | RIS | RefWorks Download
We consider orientation problems on mixed graphs in which the goal is to obtain a directed graph satisfying certain connectivity requirements.
Journal: Discrete Applied Mathematics - DAM , vol. 116, no. 3, pp. 271-278, 2002
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...On the theoretical side, Arkin and Hassin [1] studied the decision problem of orienting a mixed graph to admit directed paths for a given set of source-target vertex pairs and showed that this problem is NP-complete...

    Dana Silverbushet al. Optimally Orienting Physical Networks

    • ...Hakimi et al. [4] studied a restricted version of the problem where the list of vertex pairs includes all possible pairs, giving a quadratic time algorithm for it. Another variant of the problem was studied in [1] and [5], where rather than maximizing the total number of pairs, an algorithm was given to decide if one can satisfy all given pairs...

    Alexander Medvedovskyet al. An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its ...

    • ...Hardness result. Arkin and Hassin [1] showed that it is NP-complete to decide whether, for a given mixed graph G and a collection of source-target pairs P , the graph G can be oriented to satisfy all pairs in P . Their reduction, based on the 3-satisfiability problem, guarantees that for every k ∈ N there exists an assignment with k satisfied clauses if and only if there exists an orientation with k satisfied pairs...

    Michael Elberfeldet al. Approximation Algorithms for Orienting Mixed Graphs

Sort by: