{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T03:42:53Z","timestamp":1742960573201,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_2","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"16-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Most Imbalanced Orientation of a Graph"],"prefix":"10.1007","author":[{"given":"Walid","family":"Ben-Ameur","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Glorieux","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Neto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"2_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-540-72870-2_16","volume-title":"Algorithmic Aspects in Information and Management","author":"Y Asahiro","year":"2007","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. In: Kao, M.-Y., Li, X.-Y. (eds.) AAIM 2007. LNCS, vol. 4508, pp. 167\u2013177. Springer, Heidelberg (2007)"},{"key":"2_CR2","unstructured":"Asahiro, Y., Miyano, E., Ono, H.: Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree. In: Proceedings of the Fourteenth Computing: the Australasian Theory Symposium(CATS2008), Wollongong, NSW, Australia (2008)"},{"key":"2_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/978-3-319-08001-7_3","volume-title":"Approximation and Online Algorithms","author":"Y Asahiro","year":"2014","unstructured":"Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Degree-constrained graph orientation: maximum satisfaction and minimum violation. In: Kaklamanis, C., Pruhs, K. (eds.) WAOA 2013. LNCS, vol. 8447, pp. 24\u201336. Springer, Heidelberg (2014)"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., Gutin, G.: Orientations of graphs and digraphs in Digraphs: Theory, Algorithms and applications, 2nd edition, pp. 417\u2013472. Springer (2009)","DOI":"10.1007\/978-1-84800-998-1_11"},{"issue":"1","key":"2_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.dam.2004.12.001","volume":"48","author":"T Biedl","year":"2005","unstructured":"Biedl, T., Chan, T., Ganjali, Y., Hajiaghayi, M., Wood, D.R.: Balanced vertex-orderings of graphs. Discrete Applied Mathematics 48(1), 27\u201348 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"2_CR6","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(91)90020-3","volume":"86","author":"M Chrobak","year":"1991","unstructured":"Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theoretical Computer Sciences 86, 243\u2013266 (1991)","journal-title":"Theoretical Computer Sciences"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1002\/net.3230150409","volume":"15","author":"F Chung","year":"1985","unstructured":"Chung, F., Garey, M., Tarjan, R.: Strongly connected orientations of mixed multigraphs. Networks 15, 477\u2013484 (1985)","journal-title":"Networks"},{"key":"2_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0095-8956(78)90078-3","volume":"24","author":"V Chv\u00e1tal","year":"1978","unstructured":"Chv\u00e1tal, V., Thomassen, C.: Distances in orientation of graphs. Journal of Combinatorial Theory, Series B 24, 61\u201375 (1978)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn. Springer (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"issue":"4","key":"2_CR10","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1002\/jgt.10160","volume":"45","author":"F Fomin","year":"2004","unstructured":"Fomin, F., Matamala, M., Rapaport, I.: Complexity of approximating the oriented diameter of chordal graphs. Journal of Graph Theory 45(4), 255\u2013269 (2004)","journal-title":"Journal of Graph Theory"},{"key":"2_CR11","volume-title":"Flows in networks","author":"LR Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in networks. Princeton University Press, Princeton (1962)"},{"key":"2_CR12","first-page":"353","volume":"18","author":"A Frank","year":"1976","unstructured":"Frank, A., Gy\u00e1rf\u00e1s, A.: How to orient the edges of a graph? Colloquia Mathematica Societatis J\u00e1nos Bolyai 18, 353\u2013364 (1976)","journal-title":"Colloquia Mathematica Societatis J\u00e1nos Bolyai"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.4153\/CMB-1972-036-5","volume":"15","author":"F Harary","year":"1971","unstructured":"Harary, F., Krarup, J., Schwenk, A.: Graphs suppressible to an edge. Canadian Mathematical Bulletin 15, 201\u2013204 (1971)","journal-title":"Canadian Mathematical Bulletin"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1007\/11533719_86","volume-title":"Computing and Combinatorics","author":"J K\u00e1ra","year":"2005","unstructured":"K\u00e1ra, J., Kratochv\u00edl, J., Wood, D.R.: On the complexity of the balanced vertex ordering problem. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 849\u2013858. Springer, Heidelberg (2005)"},{"key":"2_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BF02476378","volume":"15","author":"HG Landau","year":"1953","unstructured":"Landau, H.G.: On dominance relations and the structure of animal societies III. the condition for a score structure. The Bulletin of Mathematical Biophysics 15, 143\u2013148 (1953)","journal-title":"The Bulletin of Mathematical Biophysics"},{"issue":"173","key":"2_CR16","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0012-365X(01)00048-6","volume":"239","author":"D Mubayi","year":"2001","unstructured":"Mubayi, D., Will, T.G., West, D.B.: Realizing Degree Imbalances in Directed Graphs. Discrete Mathematics 239(173), 147\u2013153 (2001)","journal-title":"Discrete Mathematics"},{"key":"2_CR17","doi-asserted-by":"publisher","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"C Nash-Williams","year":"1960","unstructured":"Nash-Williams, C.: On orientations, connectivity and odd vertex pairings in finite graphs. Canadian Journal of Mathematics 12, 555\u2013567 (1960)","journal-title":"Canadian Journal of Mathematics"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"H Robbins","year":"1939","unstructured":"Robbins, H.: A theorem on graphs with an application to a problem of traffic control. American Mathematical Monthly 46, 281\u2013283 (1939)","journal-title":"American Mathematical Monthly"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T15:32:02Z","timestamp":1674228722000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}