Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(2)
Directed Graph
Satisfiability
Related Publications
(1)
Orienting Graphs to Optimize Reachability
Subscribe
Academic
Publications
A note on orientations of mixed graphs
A note on orientations of mixed graphs,10.1016/S0166218X(01)002281,Discrete Applied Mathematics,Esther M. Arkin,Refael Hassin
Edit
A note on orientations of mixed graphs
(
Citations: 4
)
BibTex

RIS

RefWorks
Download
Esther M. Arkin
,
Refael Hassin
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. 271278, 2002
DOI:
10.1016/S0166218X(01)002281
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.
(
www.sciencedirect.com
)
(
www.informatik.unitrier.de
)
(
linkinghub.elsevier.com
)
Citation Context
(3)
...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 sourcetarget vertex pairs and showed that this problem is NPcomplete...
Dana Silverbush
,
et 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 Medvedovsky
,
et al.
An Algorithm for Orienting Graphs Based on CauseEffect Pairs and Its ...
...Hardness result. Arkin and Hassin [
1
] showed that it is NPcomplete to decide whether, for a given mixed graph G and a collection of sourcetarget pairs P , the graph G can be oriented to satisfy all pairs in P . Their reduction, based on the 3satisfiability 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 Elberfeld
,
et al.
Approximation Algorithms for Orienting Mixed Graphs
References
(3)
The Directed Subgraph Homeomorphism Problem
(
Citations: 267
)
Steven Fortune
,
John E. Hopcroft
,
James Wyllie
Journal:
Theoretical Computer Science  TCS
, vol. 10, no. 2, pp. 111121, 1980
On orientations and shortest paths
(
Citations: 6
)
Refael Hassin
Journal:
Linear Algebra and Its Applications  LINEAR ALGEBRA APPL
, vol. 114115, pp. 589602, 1989
Some remarks on Arcconnectivity, vertex splitting, and orientation in graphs and digraphs
(
Citations: 24
)
Bill Jackson
Journal:
Journal of Graph Theory  JGT
, vol. 12, no. 3, pp. 429436, 1988
Sort by:
Citations
(4)
Optimally Orienting Physical Networks
(
Citations: 3
)
Dana Silverbush
,
Michael Elberfeld
,
Roded Sharan
Conference:
Research in Computational Molecular Biology  RECOMB
, pp. 424436, 2011
An Algorithm for Orienting Graphs Based on CauseEffect Pairs and Its Applications to Orienting Protein Networks
(
Citations: 5
)
Alexander Medvedovsky
,
Vineet Bafna
,
Uri Zwick
,
Roded Sharan
Conference:
Algorithms in Bioinformatics  WABI
, pp. 222232, 2008
Improvement of power electronics education with an interactive electronic book based on Mathcad
(
Citations: 2
)
M. Sanz
,
A. Lazaro
,
C. Fernandez
,
P. Zumel
,
A. Barrado
,
E. Olias
Conference:
IEEE Workshop Power Electronics Education, 2005  PEEW
, 2005
Approximation Algorithms for Orienting Mixed Graphs
(
Citations: 1
)
Michael Elberfeld
,
Danny Segev
,
Colin R. Davidson
,
Dana Silverbush
,
Roded Sharan