{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:29:55Z","timestamp":1773271795727,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642214578","type":"print"},{"value":"9783642214585","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_35","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T17:11:27Z","timestamp":1309194687000},"page":"416-428","source":"Crossref","is-referenced-by-count":4,"title":["Approximation Algorithms for Orienting Mixed Graphs"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elberfeld","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danny","family":"Segev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Colin R.","family":"Davidson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Silverbush","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roded","family":"Sharan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"35_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/S0166-218X(01)00228-1","volume":"116","author":"E.M. Arkin","year":"2002","unstructured":"Arkin, E.M., Hassin, R.: A note on orientations of mixed graphs. Discrete Applied Mathematics\u00a0116(3), 271\u2013278 (2002)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"35_CR2","doi-asserted-by":"publisher","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 Journal on Discrete Mathematics\u00a012(3), 289\u2013297 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"35_CR3","volume-title":"Digraphs: Theory, Algorithms and Applications","author":"J. Bang-Jensen","year":"2008","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, Heidelberg (2008)","edition":"2"},{"issue":"2","key":"35_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1038\/nrg1272","volume":"5","author":"A.-L. Barab\u00e1si","year":"2004","unstructured":"Barab\u00e1si, A.-L., Oltvai, Z.N.: Network biology: understanding the cell\u2019s functional organization. Nature Reviews Genetics\u00a05(2), 101\u2013113 (2004)","journal-title":"Nature Reviews Genetics"},{"issue":"9","key":"35_CR5","doi-asserted-by":"publisher","first-page":"716","DOI":"10.2307\/2321858","volume":"87","author":"F. Boesch","year":"1980","unstructured":"Boesch, F., Tindell, R.: Robbins\u2019s theorem for mixed multigraphs. The American Mathematical Monthly\u00a087(9), 716\u2013719 (1980)","journal-title":"The American Mathematical Monthly"},{"issue":"7","key":"35_CR6","doi-asserted-by":"publisher","first-page":"1188","DOI":"10.1016\/j.jcss.2008.05.002","volume":"74","author":"J. Chen","year":"2008","unstructured":"Chen, J., Fomin, F.V., Liu, Y., Lu, S., Villanger, Y.: Improved algorithms for feedback vertex set problems. Journal of Computer and System Sciences\u00a074(7), 1188\u20131198 (2008)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"35_CR7","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1002\/net.3230150409","volume":"15","author":"F.R.K. Chung","year":"1985","unstructured":"Chung, F.R.K., Garey, M.R., Tarjan, R.E.: Strongly connected orientations of mixed multigraphs. Networks\u00a015(4), 477\u2013484 (1985)","journal-title":"Networks"},{"key":"35_CR8","volume-title":"Handbook of Graphs and Networks: From the Genome to the Internet","author":"R. Cohen","year":"2002","unstructured":"Cohen, R., Havlin, S., ben-Avraham, D.: Structural properties of scale-free networks. In: Handbook of Graphs and Networks: From the Genome to the Internet. Wiley-VCH, Weinheim (2002)"},{"key":"35_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1007\/978-3-642-19754-3_12","volume-title":"Theory and Practice of Algorithms in (Computer) Systems","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\u2013effect pairs (To appear). In: Marchetti-Spaccamela, A., Segal, M. (eds.) TAPAS 2011. LNCS, vol.\u00a06595, pp. 104\u2013115. Springer, Heidelberg (2011)"},{"issue":"21","key":"35_CR10","doi-asserted-by":"publisher","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. The promise and the peril. The FEB Journal\u00a0272(21), 5391\u20135399 (2005)","journal-title":"The FEB Journal"},{"key":"35_CR11","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"35_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/3-540-10003-2_73","volume-title":"Automata, Languages and Programming","author":"G.N. Frederickson","year":"1980","unstructured":"Frederickson, G.N., Johnson, D.B.: Generating and searching sets induced by networks. In: ICALP 1980. LNCS, vol.\u00a085, pp. 221\u2013233. Springer, Heidelberg (1980)"},{"key":"35_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-642-15294-8_18","volume-title":"Algorithms in Bioinformatics","author":"I. Gamzu","year":"2010","unstructured":"Gamzu, I., Segev, D., Sharan, R.: Improved orientations of physical networks. In: Moulton, V., Singh, M. (eds.) WABI 2010. LNCS, vol.\u00a06293, pp. 215\u2013225. Springer, Heidelberg (2010)"},{"issue":"6868","key":"35_CR14","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1038\/415141a","volume":"415","author":"A.-C. Gavin","year":"2002","unstructured":"Gavin, A., B\u00f6sche, M., Krause, R., Grandi, P., Marzioch, M., Bauer, A., Schultz, J., Rick, J.M., Michon, A.-M., Cruciat, C.-M., Remor, M., H\u00f6fert, C., Schelder, M., Brajenovic, M., Ruffner, H., Merino, A., Klein, K., Hudak, M., Dickson, D., Rudi, T., Gnau, V., Bauch, A., Bastuck, S., Huhse, B., Leutwein, C., Heurtier, M.-A., Copley, R.R., Edelmann, A., Querfurth, E., Rybin, V., Drewes, G., Raida, M., Bouwmeester, T., Bork, P., Seraphin, B., Kuster, B., Neubauer, G., Superti-Furga, G.: Functional organization of the yeast proteome by systematic analysis of protein complexes. Nature\u00a0415(6868), 141\u2013147 (2002)","journal-title":"Nature"},{"issue":"5","key":"35_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/S0020-0190(97)00129-4","volume":"63","author":"S.L. Hakimi","year":"1997","unstructured":"Hakimi, S.L., Schmeichel, E.F., Young, N.E.: Orienting graphs to optimize reachability. Information Processing Letters\u00a063(5), 229\u2013235 (1997)","journal-title":"Information Processing Letters"},{"issue":"4","key":"35_CR16","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"35_CR17","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"35_CR18","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-540-87361-7_19","volume-title":"Algorithms in Bioinformatics","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. In: Crandall, K.A., Lagergren, J. (eds.) WABI 2008. LNCS (LNBI), vol.\u00a05251, pp. 222\u2013232. Springer, Heidelberg (2008)"},{"issue":"2","key":"35_CR19","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"M.E.J. Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Review\u00a045(2), 167\u2013256 (2003)","journal-title":"SIAM Review"},{"issue":"5","key":"35_CR20","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"H.E. Robbins","year":"1939","unstructured":"Robbins, H.E.: A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly\u00a046(5), 281\u2013283 (1939)","journal-title":"The American Mathematical Monthly"},{"key":"35_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-642-20036-6_39","volume-title":"Research in Computational Molecular Biology","author":"D. Silverbush","year":"2011","unstructured":"Silverbush, D., Elberfeld, M., Sharan, R.: Optimally orienting physical networks. In: Bafna, V., Sahinalp, S.C. (eds.) RECOMB 2011. LNCS, vol.\u00a06577, pp. 424\u2013436. Springer, Heidelberg (2011)"},{"issue":"6","key":"35_CR22","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"R.E. Tarjan","year":"1974","unstructured":"Tarjan, R.E.: A note on finding the bridges of a graph. Information Processing Letters\u00a02(6), 160\u2013161 (1974)","journal-title":"Information Processing Letters"},{"issue":"2-3","key":"35_CR23","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1089\/1066527041410382","volume":"11","author":"C.-H. Yeang","year":"2004","unstructured":"Yeang, C., Ideker, T., Jaakkola, T.: Physical network models. Journal of Computational Biology\u00a011(2-3), 243\u2013262 (2004)","journal-title":"Journal of Computational Biology"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,29]],"date-time":"2019-03-29T09:40:12Z","timestamp":1553852412000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}