On the Approximability of Reachability-Preserving Network Orientations

References

• Alon , [Alon and Spencer 00] N. and Spencer , J. H. 2000 . The Probabilistic Method , New York : Wiley Interscience .
   Google Scholar
• Bang-Jensen , [Bang-Jensen and Gutin 08] J. and Gutin , G. 2008 . Digraphs: Theory, Algorithms and Applications , New York : Springer .
   Google Scholar
• Dorn , [Dorn et al. 11] B. , Hüffner , F. , Krüger , D. , Niedermeier , R. and Uhlmann , J. 2011 . “Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs.” . In Proceedings of the 1st International ICST Conference on Theory and Practice of Algorithms in (Computer) Systems (TAPAS 2011) , 104 – 115 . New York : Springer . Lecture Notes in Computer Science 6595
   Google Scholar
• Elberfeld , [Elberfeld et al. 11] M. , Segev , D. , Davidson , C. R. , Silverbush , D. and Sharan , R. 2011 . “Approximation Algorithms for Orienting Mixed Graphs.” . In Proceedings of the 22nd Annual Symposium on Combinatorial Pattern Matching (CPM 2011) , 416 – 428 . New York : Springer . Lecture Notes in Computer Science 6661
   Google Scholar
• Fields , [Fields 05] S. 2005 . “High-Throughput Two-Hybrid Analysis. The Promise and the Peril.” . FEBS Journal , 272 ( 21 ) : 5391 – 5399 .
   Google Scholar
• Frederickson , [Frederickson and Johnson 80] G. N. and Johnson , D. B. 1980 . “Generating and Searching Sets Induced by Networks.” . In Proceedings 7th International Colloquium on Automata, Languages and Programming (ICALP 1980) , 221 – 233 . New York : Springer . Lecture Notes in Computer Science 85
   Google Scholar
• Gamzu , [Gamzu and Segev 10] I. and Segev , D. 2010 . “A Sublogarithmic Approximation for Highway and Tollbooth Pricing.” . In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) , 582 – 593 . New York : Springer . Lecture Notes in Computer Science 6198
   Google Scholar
• Gamzu , [Gamzu et al. 10] I. , Segev , D. and Sharan , R. 2010 . “Improved Orientations of Physical Networks.” . In Proceedings of the 10th International Workshop on Algorithms in Bioinformatics (WABI 2010) , 215 – 225 . New York : Springer . Lecture Notes in Computer Science 6293
   Google Scholar
• Gavin , [Gavin et al. 02] A. , Bösche , M. , Krause , R. , Grandi , P. Marzioch , M. 2002 . “Functional Oorganization of the Yeast Proteome by Systematic Analysis of Protein Complexes.” . Nature , 415 ( 6868 ) : 141 – 147 .
   PubMed Web of Science ®Google Scholar
• Gitter , [Gitter et al. 11] A. , Klein-Seetharaman , J. , Gupta , A. and Bar-Joseph , Z. 2011 . “Discovering Pathways by Orienting Edges in Protein Interaction Networks.” . Nucleic Acids Research , 39 ( 4 ) : e22
   Google Scholar
• Hakimi , [Hakimi et al. 97] S. L. , Schmeichel , E. F. and Young , N. E. 1997 . “Orienting Graphs to Optimize Reachability.” . Information Processing Letters , 63 ( 5 ) : 229 – 235 .
   Google Scholar
• Håstad , [Håstad 01] J. 2001 . “Some Optimal Inapproximability Results.” . Journal of the ACM , 48 ( 4 ) : 798 – 859 .
   Google Scholar
• Hochbaum , [Hochbaum 83] D. S. 1983 . “Efficient Bounds for the Stable Set, Vertex Cover and Set Packing Problems.” . Discrete Applied Mathematics , 6 ( 3 ) : 243 – 254 .
   Google Scholar
• Kann , [Kann et al. 96] V. , Lagergren , J. and Panconesi , A. 1996 . “Approximability of Maximum Splitting of k-Sets and Some Other APX-Complete Problems.” . Information Processing. Letters , 58 ( 3 ) : 105 – 110 .
   Google Scholar
• Lewin , [Lewin et al. 06] M. , Livnat , D. and Zwick , U. 2006 . “Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems.” . In Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO 2002) , 67 – 82 . New York : Springer . Lecture Notes in Computer Science 2337
   Google Scholar
• Medvedovsky , [Medvedovsky 09] A. “An Algorithm for Orienting Graphs Based on Cause–Effect Pairs and Its Applications to Orienting Protein Networks.” . Master's thesis, Tel-Aviv University, Israel, 2009. Available online at http://www.cs.tau.ac.il/roded/Sasha-thesis.pdf
   Google Scholar
• Medvedovsky , [Medvedovsky et al. 08] A. , Bafna , V. , Zwick , U. and Sharan , R. 2008 . “An Algorithm for Orienting Graphs Based on Cause–Effect Pairs and Its Applications to Orienting Protein Networks.” . In Proceedings of the 8th International Workshop on Algorithms in Bioinformatics (WABI 2008) , 222 – 232 . New York : Springer . Lecture Notes in Computer Science 5251
   Google Scholar
• Ourfali , [Ourfali et al. 07] O. , Shlomi , T. , Ideker , T. , Ruppin , E. and Sharan , R. 2007 . “SPINE: A Framework for Signaling-Regulatory Pathway Inference from Cause–Effect Experiments.” . Bioinformatics , 23 ( 13 ) : i359 – i366 .
   Google Scholar
• Robbins , [Robbins 30] H. E. 1939 . “A Theorem on Graphs, with an Application to a Problem of Traffic Control.” . American Mathematical Monthly , 46 ( 5 ) : 281 – 283 .
   Google Scholar
• Silverbush , [Silverbush et al. 11] D. , Elberfeld , M. and Sharan , R. 2011 . “Optimally Orienting Physical Networks.” . In Proceedings of the 15th Annual International Conference on Research in Computational Molecular Biology (RECOMB 2011) , 424 – 436 . New York : Springer . Lecture Notes in Computer Science 6577
   Google Scholar
• Tarjan , [Tarjan 72] R. E. 1972 . “Depth-First Search and Linear Graph Algorithms.” . SIAM Journal on Computing , 1 ( 2 ) : 146 – 160 .
   Google Scholar
• Tarjan , [Tarjan 74] R. E. 1974 . “A Note on Finding the Bridges of a Graph.” . Information Processing Letters , 2 ( 6 ) : 160 – 161 .
   Google Scholar
• Yeang , [Yeang et al. 04] C. , Ideker , T. and Jaakkola , T. 2004 . “Physical Network Models.” . Journal of Computational Biology , 11 ( 2-3 ) : 243 – 262 .
   PubMedGoogle Scholar