{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T19:36:46Z","timestamp":1649101006465},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,8,27]],"date-time":"2014-08-27T00:00:00Z","timestamp":1409097600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1007\/s00453-014-9932-2","type":"journal-article","created":{"date-parts":[[2014,8,26]],"date-time":"2014-08-26T14:07:37Z","timestamp":1409062057000},"page":"49-64","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improved Approximation for Orienting Mixed Graphs"],"prefix":"10.1007","volume":"74","author":[{"given":"Iftah","family":"Gamzu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moti","family":"Medina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,8,27]]},"reference":[{"key":"9932_CR1","doi-asserted-by":"crossref","unstructured":"Afek, Y., Bremler, A.: Self-stabilizing unidirectional network algorithms by power supply. Chic. J. Theor. Comput. Sci. 3 (1998). doi: 10.4086\/cjtcs.1998.003 .","DOI":"10.4086\/cjtcs.1998.003"},{"key":"9932_CR2","doi-asserted-by":"crossref","unstructured":"Afek, Y., Gafni, E.: Distributed algorithms for unidirectional networks. SIAM J. Comput. 23(6), 1152\u20131178 (1994)","DOI":"10.1137\/S009753979223277X"},{"issue":"3","key":"9932_CR3","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1016\/S0166-218X(01)00228-1","volume":"116","author":"EM Arkin","year":"2002","unstructured":"Arkin, E.M., Hassin, R.: A note on orientations of mixed graphs. Discrete Appl. Math. 116(3), 271\u2013278 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9932_CR4","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discrete Math. 12(3), 289\u2013297 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"9932_CR5","doi-asserted-by":"crossref","unstructured":"Becker, A.: Approximation algorithms for the loop cutset problem. In: Proceedings of the Tenth International Conference on Uncertainty in artificial intelligence, pp. 60\u201368. Morgan Kaufmann Publishers Inc., Burlington (1994)","DOI":"10.1016\/B978-1-55860-332-5.50013-4"},{"key":"9932_CR6","doi-asserted-by":"crossref","unstructured":"Blokh, D., Segev, D., Sharan, R.: Approximation algorithms and hardness results for shortest path based graph orientations. In: Combinatorial Pattern Matching, pp. 70\u201382. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31265-6_6"},{"issue":"6","key":"9932_CR7","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9932_CR8","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0167-6377(98)00021-2","volume":"22","author":"FA Chudak","year":"1998","unstructured":"Chudak, F.A., Goemans, M.X., Hochbaum, D.S., Williamson, D.P.: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4), 111\u2013118 (1998)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9932_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1748-7188-6-21","volume":"6","author":"B Dorn","year":"2011","unstructured":"Dorn, B., H\u00fcffner, F., Kr\u00fcger, D., Niedermeier, R., Uhlmann, J.: Exploiting bounded signal flow for graph orientation based on cause-effect pairs. Algorithms Mol Biol 6(1), 1\u201312 (2011)","journal-title":"Algorithms Mol Biol"},{"issue":"4","key":"9932_CR10","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1080\/15427951.2011.604554","volume":"7","author":"M Elberfeld","year":"2011","unstructured":"Elberfeld, M., Bafna, V., Gamzu, I., Medvedovsky, A., Segev, D., Silverbush, D., Zwick, U., Sharan, R.: On the approximability of reachability-preserving network orientations. Internet Math. 7(4), 209\u2013232 (2011)","journal-title":"Internet Math."},{"key":"9932_CR11","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.tcs.2012.03.044","volume":"483","author":"M Elberfeld","year":"2013","unstructured":"Elberfeld, M., Segev, D., Davidson, C.R., Silverbush, D., Sharan, R.: Approximation algorithms for orienting mixed graphs. Theor. Comput. Sci. 483, 96\u2013103 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9932_CR12","doi-asserted-by":"crossref","unstructured":"Feige, U., Goemans, M.: Approximating the value of two power proof systems, with applications to max 2sat and max dicut. In: Third Israel Symposium on the Theory of Computing and Systems, pp. 182\u2013189. IEEE (1995)","DOI":"10.1109\/ISTCS.1995.377033"},{"issue":"21","key":"9932_CR13","doi-asserted-by":"crossref","first-page":"5391","DOI":"10.1111\/j.1742-4658.2005.04973.x","volume":"272","author":"S Fields","year":"2005","unstructured":"Fields, S.: High-throughput two-hybrid analysis. FEBS J. 272(21), 5391\u20135399 (2005)","journal-title":"FEBS J."},{"key":"9932_CR14","doi-asserted-by":"crossref","unstructured":"Frederickson, G.N., Johnson, D.B.: Generating and searching sets induced by networks. In: Automata, Languages and Programming, pp. 221\u2013223. Springer, Berlin (1980)","DOI":"10.1007\/3-540-10003-2_73"},{"key":"9932_CR15","doi-asserted-by":"crossref","unstructured":"Gamzu, I., Medina, M.: Improved approximation for orienting mixed graphs. In: Structural Information and Communication Complexity, pp. 243\u2013253. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-31104-8_21"},{"key":"9932_CR16","doi-asserted-by":"crossref","unstructured":"Gamzu, I., Segev, D.: A sublogarithmic approximation for highway and tollbooth pricing. In Automata, Languages and Programming, pp. 582\u2013593. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-14165-2_49"},{"key":"9932_CR17","doi-asserted-by":"crossref","unstructured":"Gamzu, I., Segev, D., Sharan, R.: Improved orientations of physical networks. In: Algorithms in Bioinformatics, pp. 215\u2013225. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-15294-8_18"},{"issue":"6868","key":"9932_CR18","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1038\/415141a","volume":"415","author":"A-C Gavin","year":"2002","unstructured":"Gavin, A.-C., B\u00f6sche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J.M., Michon, A.-M., Cruciat, C.-M., et al.: Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature 415(6868), 141\u2013147 (2002)","journal-title":"Nature"},{"issue":"5","key":"9932_CR19","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0020-0190(97)00129-4","volume":"63","author":"SL Hakimi","year":"1997","unstructured":"Hakimi, S.L., Schmeichel, E.F., Young, N.E.: Orienting graphs to optimize reachability. Inf. Process. Lett. 63(5), 229\u2013235 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9932_CR20","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM (JACM) 48(4), 798\u2013859 (2001)","journal-title":"J. ACM (JACM)"},{"issue":"1","key":"9932_CR21","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for max-cut and other 2-variable csps? SIAM J. Comput. 37(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"key":"9932_CR22","doi-asserted-by":"crossref","unstructured":"Lewin, M., Livnat, D., Zwick, U.: Improved rounding techniques for the max 2-sat and max di-cut problems. In: Integer Programming and Combinatorial Optimization, pp. 67\u201382. Springer, Berlin (2002)","DOI":"10.1007\/3-540-47867-1_6"},{"key":"9932_CR23","doi-asserted-by":"crossref","unstructured":"Marina, M.K., Das, S.R.: Routing performance in the presence of unidirectional links in multihop wireless networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking & Computing. Association for Computing Machinery, pp. 12\u201323 (2002)","DOI":"10.1145\/513800.513803"},{"key":"9932_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-87361-7_19","volume-title":"An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and its Applications to Orienting Protein Networks","author":"A Medvedovsky","year":"2008","unstructured":"Medvedovsky, A., Bafna, V., Zwick, U., Sharan, R.: An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and its Applications to Orienting Protein Networks. Springer, Berlin (2008)"},{"issue":"11","key":"9932_CR25","doi-asserted-by":"crossref","first-page":"1437","DOI":"10.1089\/cmb.2011.0163","volume":"18","author":"D Silverbush","year":"2011","unstructured":"Silverbush, D., Elberfeld, M., Sharan, R.: Optimally orienting physical networks. J. Comput. Biol. 18(11), 1437\u20131448 (2011)","journal-title":"J. Comput. Biol."},{"issue":"2\u20133","key":"9932_CR26","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1089\/1066527041410382","volume":"11","author":"C-H Yeang","year":"2004","unstructured":"Yeang, C.-H., Ideker, T., Jaakkola, T.: Physical network models. J. Comput. Biol. 11(2\u20133), 243\u2013262 (2004)","journal-title":"J. Comput. Biol."},{"key":"9932_CR27","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3, 103\u2013128 (2007)","journal-title":"Theory Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9932-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9932-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9932-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:14Z","timestamp":1559123114000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9932-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8,27]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["9932"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9932-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,8,27]]}}}