{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T18:38:05Z","timestamp":1773859085522,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2009,11,5]],"date-time":"2009-11-05T00:00:00Z","timestamp":1257379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2011,7]]},"DOI":"10.1007\/s10878-009-9276-z","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T21:38:36Z","timestamp":1257370716000},"page":"78-96","source":"Crossref","is-referenced-by-count":26,"title":["Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree"],"prefix":"10.1007","volume":"22","author":[{"given":"Yuichi","family":"Asahiro","sequence":"first","affiliation":[]},{"given":"Jesper","family":"Jansson","sequence":"additional","affiliation":[]},{"given":"Eiji","family":"Miyano","sequence":"additional","affiliation":[]},{"given":"Hirotaka","family":"Ono","sequence":"additional","affiliation":[]},{"given":"Kouhei","family":"Zenmyo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,11,5]]},"reference":[{"issue":"2","key":"9276_CR1","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1142\/S0129054107004644","volume":"18","author":"Y Asahiro","year":"2007","unstructured":"Asahiro Y, Miyano E, Ono H, Zenmyo K (2007) Graph orientation algorithms to minimize the maximum outdegree. Int J Found Comput Sci 18(2):197\u2013216","journal-title":"Int J Found Comput Sci"},{"issue":"1","key":"9276_CR2","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 MT, Wood DR (2005) Balanced vertex-orderings of graphs. Discrete Appl Math 48(1):27\u201348","journal-title":"Discrete Appl Math"},{"key":"9276_CR3","unstructured":"Brodal GS, Fagerberg R (1999) Dynamic representations of sparse graphs. In: Proc WADS1999. LNCS, vol\u00a01663, pp\u00a0342\u2013351"},{"issue":"2","key":"9276_CR4","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(2):243\u2013266","journal-title":"Theor Comput Sci"},{"key":"9276_CR5","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(75)90061-1","volume":"18","author":"V Chv\u0301atal","year":"1975","unstructured":"Chv\u0301atal V (1975) A combinatorial theorem in plane geometry. J\u00a0Comb Theory, Ser\u00a0B 18:39\u201341","journal-title":"J\u00a0Comb Theory, Ser\u00a0B"},{"key":"9276_CR6","volume-title":"Introduction to algorithms","author":"T Cormen","year":"1990","unstructured":"Cormen T, Leiserson C, Rivest R (1990) Introduction to algorithms. MIT Press, Cambridge"},{"issue":"4","key":"9276_CR7","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1002\/jgt.10160","volume":"45","author":"FV Fomin","year":"2004","unstructured":"Fomin FV, Matamala M, Rapaport I (2004) Complexity of approximating the oriented diameter of chordal graphs. J\u00a0Graph Theory 45(4):255\u2013269","journal-title":"J\u00a0Graph Theory"},{"key":"9276_CR8","volume-title":"Computers and intractability: A\u00a0guide to the theory of NP-completeness","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability: A\u00a0guide to the theory of NP-completeness. W\u00a0H\u00a0Freeman, New York"},{"issue":"5","key":"9276_CR9","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"AV Goldberg","year":"1998","unstructured":"Goldberg AV, Rao S (1998) Beyond the flow decomposition barrier. J\u00a0ACM 45(5):783\u2013797","journal-title":"J\u00a0ACM"},{"issue":"2","key":"9276_CR10","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E Horowitz","year":"1976","unstructured":"Horowitz E, Sahni S (1976) Exact and approximate algorithms for scheduling nonidentical processors. J\u00a0ACM 23(2):317\u2013327","journal-title":"J\u00a0ACM"},{"key":"9276_CR11","doi-asserted-by":"crossref","unstructured":"K\u00e1ra J, Kratochv\u00edl J, Wood DR (2005) On the complexity of the balanced vertex ordering problem. In: Proc COCOON2005. LNCS, vol\u00a03595, pp\u00a0849\u2013858","DOI":"10.1007\/11533719_86"},{"key":"9276_CR12","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1006\/jagm.1994.1044","volume":"17","author":"V King","year":"1994","unstructured":"King V, Rao S, Tarjan R (1994) A faster deterministic maximum flow algorithm. J\u00a0Algorithms 17:447\u2013474","journal-title":"J\u00a0Algorithms"},{"key":"9276_CR13","unstructured":"Kowalik L (2006) Approximation scheme for lowest outdegree orientation and graph density measures. In: Proc ISAAC2006. LNCS, vol 4288, pp 557\u2013566"},{"issue":"3","key":"9276_CR14","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"JK Lenstra","year":"1990","unstructured":"Lenstra JK, Shmoys DB, Tardos E (1990) Approximation algorithms for scheduling unrelated parallel machines. Math Program 46(3):259\u2013271","journal-title":"Math Program"},{"key":"9276_CR15","volume-title":"Art gallery theorems and algorithms","author":"J O\u2019Rourke","year":"1987","unstructured":"O\u2019Rourke J (1987) Art gallery theorems and algorithms. Oxford University Press, Oxford"},{"key":"9276_CR16","volume-title":"Scheduling: Theory, algorithms, and systems","author":"M Pinedo","year":"2002","unstructured":"Pinedo M (2002) Scheduling: Theory, algorithms, and systems, 2nd\u00a0edn. Prentice-Hall, Englewood Cliffs","edition":"2"},{"key":"9276_CR17","volume-title":"Combinatorial optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization. Springer, Berlin"},{"key":"9276_CR18","first-page":"203","volume":"2","author":"P Schuurman","year":"1999","unstructured":"Schuurman P, Woeginger GJ (1999) Polynomial time approximation algorithms for machine scheduling: Ten open problems. J\u00a0Sched 2:203\u2013213","journal-title":"J\u00a0Sched"},{"issue":"1\u20133","key":"9276_CR19","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.dam.2003.07.007","volume":"143","author":"V Venkateswaran","year":"2004","unstructured":"Venkateswaran V (2004) Minimizing maximum indegree. Discrete Appl Math 143(1\u20133):374\u2013378","journal-title":"Discrete Appl Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9276-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9276-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9276-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:15Z","timestamp":1559276295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9276-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,11,5]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,7]]}},"alternative-id":["9276"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9276-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,11,5]]}}}