{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:15:05Z","timestamp":1761621305083,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,2,21]],"date-time":"2017-02-21T00:00:00Z","timestamp":1487635200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s10878-017-0117-1","type":"journal-article","created":{"date-parts":[[2017,2,21]],"date-time":"2017-02-21T09:48:08Z","timestamp":1487670488000},"page":"637-669","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the most imbalanced orientation of a graph"],"prefix":"10.1007","volume":"36","author":[{"given":"Walid","family":"Ben-Ameur","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3720-5619","authenticated-orcid":false,"given":"Antoine","family":"Glorieux","sequence":"additional","affiliation":[]},{"given":"Jos\u00e9","family":"Neto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,21]]},"reference":[{"key":"117_CR1","doi-asserted-by":"crossref","unstructured":"Asahiro Y, Miyano E, Ono H, Zenmyo K (2007) Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. In: Proceedings of the 3rd international conference on algorithmic aspects in information and management (AAIM2007). LNCS 4508, pp 167\u2013177","DOI":"10.1007\/978-3-540-72870-2_16"},{"key":"117_CR2","unstructured":"Asahiro Y, Miyano E, Ono H (2008) 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"},{"key":"117_CR3","doi-asserted-by":"crossref","unstructured":"Asahiro Y, Jansson J, Miyano E, Ono H (2014) Degree constrained graph orientation: maximum satisfaction and minimum violation. WAOA 2013, LNCS 8447, pp 24\u201336","DOI":"10.1007\/978-3-319-08001-7_3"},{"key":"117_CR4","volume-title":"Orientations of graphs and digraphs in digraphs: theory, algorithms and applications","author":"J Bang-Jensen","year":"2009","unstructured":"Bang-Jensen J, Gutin G (2009) Orientations of graphs and digraphs in digraphs: theory, algorithms and applications, 2nd edn. Springer, Berlin","edition":"2"},{"issue":"4","key":"117_CR5","doi-asserted-by":"crossref","first-page":"1541","DOI":"10.1137\/090759033","volume":"24","author":"W Ben-Ameur","year":"2010","unstructured":"Ben-Ameur W, Hadji M (2010) Designing Steiner networks with unicyclic connected components: an easy problem. SIAM J Discrete Math 24(4):1541\u20131557","journal-title":"SIAM J Discrete Math"},{"issue":"1","key":"117_CR6","doi-asserted-by":"crossref","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 DR (2005) Balanced vertex-orderings of graphs. Discrete Appl Math 48(1):27\u201348","journal-title":"Discrete Appl Math"},{"key":"117_CR7","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0304-3975(91)90020-3","volume":"86","author":"M Chrobak","year":"1991","unstructured":"Chrobak M, Eppstein D (1991) Planar orientations with low out-degree and compaction of adjacency matrices. Theor Comput Sci 86:243\u2013266","journal-title":"Theor Comput Sci"},{"key":"117_CR8","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1002\/net.3230150409","volume":"15","author":"F Chung","year":"1985","unstructured":"Chung F, Garey M, Tarjan R (1985) Strongly connected orientations of mixed multigraphs. Networks 15:477\u2013484","journal-title":"Networks"},{"key":"117_CR9","doi-asserted-by":"crossref","unstructured":"Ch $$\\acute{{\\rm v}}$$ v \u00b4 atal V, Thomassen C (1978) Distances in orientation of graphs. J Comb Theory Ser B 24:61\u201375","DOI":"10.1016\/0095-8956(78)90078-3"},{"key":"117_CR10","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1006\/jctb.1994.1029","volume":"61","author":"M Degraaf","year":"1994","unstructured":"Degraaf M, Schrijver A (1994) Grid minors of graphs on the torus. J Comb Theory Ser B 61:57\u201362","journal-title":"J Comb Theory Ser B"},{"key":"117_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph theory","author":"R Diestel","year":"2010","unstructured":"Diestel R (2010) Graph theory, 4th edn. Springer, Berlin","edition":"4"},{"issue":"4","key":"117_CR12","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1002\/jgt.10160","volume":"45","author":"F Fomin","year":"2004","unstructured":"Fomin F, Matamala M, Rapaport I (2004) Complexity of approximating the oriented diameter of chordal graphs. J Graph Theory 45(4):255\u2013269","journal-title":"J Graph Theory"},{"key":"117_CR13","volume-title":"Flows in networks","author":"LR Ford","year":"1962","unstructured":"Ford LR, Fulkerson DR (1962) Flows in networks. Princeton University Press, Princeton"},{"key":"117_CR14","first-page":"353","volume":"18","author":"A Frank","year":"1976","unstructured":"Frank A, Gy\u00e1rf\u00e1s A (1976) How to orient the edges of a graph? Colloq Math Soc J\u00e1nos Bolyai 18:353\u2013364","journal-title":"Colloq Math Soc J\u00e1nos Bolyai"},{"key":"117_CR15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.4153\/CMB-1972-036-5","volume":"15","author":"F Harary","year":"1971","unstructured":"Harary F, Krarup J, Schwenk A (1971) Graphs suppressible to an edge. Can Math Bull 15:201\u2013204","journal-title":"Can Math Bull"},{"key":"117_CR16","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds J, Johnson EL (1973) Matching, Euler tours and the Chinese postman problem. Math Program 5:88\u2013124","journal-title":"Math Program"},{"key":"117_CR17","doi-asserted-by":"crossref","unstructured":"K\u00e1ra J, Kratochv\u00edl J, Wood DR (2005) On the complexity of the balanced vertex ordering problem. In: Proceedings of COCOON2005. LNCS 3595, pp 849\u2013858","DOI":"10.1007\/11533719_86"},{"key":"117_CR18","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02476378","volume":"15","author":"HG Landau","year":"1953","unstructured":"Landau HG (1953) On dominance relations and the structure of animal societies III. The condition for a score structure. Bull Math Biophys 15:143\u2013148","journal-title":"Bull Math Biophys"},{"issue":"173","key":"117_CR19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/S0012-365X(01)00048-6","volume":"239","author":"D Mubayi","year":"2001","unstructured":"Mubayi D, Will TG, West DB (2001) Realizing degree imbalances in directed graphs. Discrete Math 239(173):147\u2013153","journal-title":"Discrete Math"},{"key":"117_CR20","doi-asserted-by":"crossref","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"C Nash-Williams","year":"1960","unstructured":"Nash-Williams C (1960) On orientations, connectivity and odd vertex pairings in finite graphs. Can J Math 12:555\u2013567","journal-title":"Can J Math"},{"key":"117_CR21","doi-asserted-by":"crossref","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"H Robbins","year":"1939","unstructured":"Robbins H (1939) A theorem on graphs with an application to a problem of traffic control. Am Math Mon 46:281\u2013283","journal-title":"Am Math Mon"},{"key":"117_CR22","doi-asserted-by":"crossref","unstructured":"Schaefer TJ (1978) The complexity of satisfiability problems. In: Proceedings of the 10th annual ACM symposium on theory of computing, pp 216\u2013226","DOI":"10.1145\/800133.804350"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0117-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0117-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0117-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T18:56:35Z","timestamp":1568832995000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0117-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,21]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["117"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0117-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,2,21]]}}}