{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T15:18:29Z","timestamp":1725981509546},"publisher-location":"Cham","reference-count":47,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319718392"},{"type":"electronic","value":"9783319718408"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-71840-8_12","type":"book-chapter","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T20:19:25Z","timestamp":1529353165000},"page":"575-607","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lexicographic Orientation Algorithms"],"prefix":"10.1007","author":[{"given":"Jing","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,19]]},"reference":[{"issue":"3","key":"12_CR1","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1002\/jgt.3190140310","volume":"14","author":"J Bang-Jensen","year":"1990","unstructured":"J.\u00a0Bang-Jensen. Locally semicomplete digraphs: a generalization of tournaments. J. Graph Theory, 14(3):371\u2013390, 1990.","journal-title":"J. Graph Theory"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.dam.2015.04.020","volume":"193","author":"J Bang-Jensen","year":"2015","unstructured":"J.\u00a0Bang-Jensen and C.J. Casselgren. Restricted cycles factors and arc-decompositions of digraphs. Discrete Appl. Math., 193:80\u201393, 2015.","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1002\/jgt.3190200205","volume":"20","author":"J Bang-Jensen","year":"1995","unstructured":"J.\u00a0Bang-Jensen and J.\u00a0Huang. Quasi-transitive digraphs. J. Graph Theory, 20(2):141\u2013161, 1995.","journal-title":"J. Graph Theory"},{"issue":"3","key":"12_CR4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1002\/jgt.22157","volume":"87","author":"J Bang-Jensen","year":"2018","unstructured":"J.\u00a0Bang-Jensen, J.\u00a0Huang, and X\u00a0Zhu. Completing orientations of partially oriented graphs. J. Graph Theory, 87(3) 285\u2013304, 2018.","journal-title":"J. Graph Theory"},{"issue":"9","key":"12_CR5","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1080\/00029890.1980.11995131","volume":"87","author":"F Boesch","year":"1980","unstructured":"F.\u00a0Boesch and R.\u00a0Tindell. Robbins\u2019s theorem for mixed multigraphs. Amer. Math. Mon., 87(9):716\u2013719, 1980.","journal-title":"Amer. Math. Mon."},{"key":"12_CR6","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1016\/j.aim.2014.11.011","volume":"270","author":"M Chudnovsky","year":"2015","unstructured":"M.\u00a0Chudnovsky, A.\u00a0Scott, and P.D. Seymour. Disjoint paths in tournaments. Adv. Math., 270:582\u2013597, 2015.","journal-title":"Adv. Math."},{"key":"12_CR7","unstructured":"O.D.\u00a0de Gevigney. On Frank\u2019s conjecture on $$k$$-connected orientations. Preprint arXiv:1212.4086v1 , December 2012."},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s13173-012-0065-7","volume":"18","author":"OD Gevigney de","year":"2012","unstructured":"O.D.\u00a0de Gevigney, S.\u00a0Klein, V.H. Nguyen, and Z.\u00a0Szigeti. Sandwich problems on orientations. J. Brazilian Comput. Soc., 18:85\u201393, 2012.","journal-title":"J. Brazilian Comput. Soc."},{"issue":"2","key":"12_CR9","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X Deng","year":"1996","unstructured":"X.\u00a0Deng, P.\u00a0Hell, and J.\u00a0Huang. Linear-time representation algorithms for proper circular-arc graphs and proper interval graphs. SIAM J. Comput., 25(2):390\u2013403, 1996.","journal-title":"SIAM J. Comput."},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s004939970003","volume":"19","author":"T Feder","year":"1999","unstructured":"T.\u00a0Feder, P.\u00a0Hell, and J.\u00a0Huang. List homomorphisms and circular arc graphs. Combinatorica, 19:487\u2013505, 1999.","journal-title":"Combinatorica"},{"key":"12_CR11","volume-title":"Flows in networks","author":"LR Ford Jr","year":"1962","unstructured":"L.R. Ford, Jr. and D.R. Fulkerson. Flows in networks. Princeton University Press, Princeton, NJ, 1962."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"S.\u00a0Fortune, J.E. Hopcroft, and J.\u00a0Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111\u2013121, 1980.","journal-title":"Theor. Comput. Sci."},{"key":"12_CR13","unstructured":"T.\u00a0Gallai. On directed paths and circuits. In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 115\u2013118. Academic Press, 1968."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"T.\u00a0Gallai. Transitiv orientbare Graphen. Acta Math. Acad. Sci. Hungar, 18:25\u201366, 1967.","journal-title":"Acta Math. Acad. Sci. Hungar"},{"key":"12_CR15","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and intractability. W. H. Freeman, San Francisco, 1979."},{"key":"12_CR16","first-page":"1370","volume":"254","author":"A Ghouila-Houri","year":"1962","unstructured":"A.\u00a0Ghouila-Houri. Caract\u00e9risation des graphes non orient\u00e9s dont on peut orienter les ar\u011btes de mani\u00e8re \u00e0 obtenir le graphe d\u2019une relation d\u2019ordre. C. R. Acad. Sci. Paris, 254:1370\u20131371, 1962.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"P.C. Gilmore and A.J. Hoffman. A characterization of comparability graphs and interval graphs. Canad. J. Math., 16:539\u2013548, 1964.","journal-title":"Canad. J. Math."},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"M.C. Golumbic. Algorithmic graph theory and perfect graphs. Academic Press, New York, 1980. With a foreword by Claude Berge.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"issue":"3","key":"12_CR19","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF02253207","volume":"18","author":"MC Golumbic","year":"1977","unstructured":"M.C. Golumbic. The complexity of comparability graph recognition and coloring. Computing, 18(3):199\u2013208, 1977.","journal-title":"Computing"},{"key":"12_CR20","first-page":"449","volume":"19","author":"MC Golumbic","year":"1995","unstructured":"M.C. Golumbic, H.\u00a0Kaplan, and R.\u00a0Shamir. Graph sandwich problems. J. Algor., 19:449\u2013473, 1995.","journal-title":"Graph sandwich problems. J. Algor."},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M Habib","year":"2000","unstructured":"M.\u00a0Habib, R.M. McConnell, C.\u00a0Paul, and L.\u00a0Viennot. Lex-BFS and partition refinement, with applications to transitive orientation, interval graphs recognition and consecutive ones testing. Theor. Comput. Sci., 234:59\u201384, 2000.","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"12_CR22","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1002\/jgt.3190200312","volume":"20","author":"P Hell","year":"1995","unstructured":"P.\u00a0Hell and J.\u00a0Huang. Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs. J. Graph Theory, 20(3):361\u2013374, 1995.","journal-title":"J. Graph Theory"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01202237","volume":"13","author":"P Hell","year":"1997","unstructured":"P.\u00a0Hell and J.\u00a0Huang. Two remarks on circular arc graphs. Graphs Combin., 13:65\u201372, 1997.","journal-title":"Graphs Combin."},{"issue":"2","key":"12_CR24","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/jctb.1995.1016","volume":"63","author":"J. Huang","year":"1995","unstructured":"J.\u00a0Huang. On the structure of local tournaments. J. Combin. Theory, Ser. B, 63(2):200\u2013221, 1995.","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1016\/j.jctb.2006.01.001","volume":"96","author":"J Huang","year":"2006","unstructured":"J.\u00a0Huang. Representation characterizations of chordal bipartite graphs. J. Combin. Theory Ser. B, 96:673\u2013683, 2006.","journal-title":"J. Combin. Theory Ser. B"},{"key":"12_CR26","unstructured":"J.\u00a0Huang. Tournament-like oriented graphs. PhD thesis, School of Computing Science, Simon Fraser University, Canada, 1992."},{"key":"12_CR27","first-page":"203","volume":"19","author":"J Huang","year":"1999","unstructured":"J.\u00a0Huang. Which digraphs are round? Australas. J. Combin., 19:203\u2013208, 1999.","journal-title":"Australas. J. Combin."},{"key":"12_CR28","doi-asserted-by":"crossref","unstructured":"P.\u00a0Klavik, J.\u00a0Kratochvil, Y.\u00a0Otachi, I.\u00a0Rutter, T.\u00a0Saitoh, M.\u00a0Saumell, and T.\u00a0Vyskocil. Extending partial representations of proper and unit interval graphs. In SWAT 2014: 14th Scandinavian Symposium and Workshops on Algorithm Theory, volume 8503 of Lect. Notes Comput. Sci., pages 253\u2013264. Springer, 2014.","DOI":"10.1007\/978-3-319-08404-6_22"},{"key":"12_CR29","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"CG Lekkerkerker","year":"1962","unstructured":"C.G. Lekkerkerker and J.Ch. Boland. Representation of a finite graph by a set of intervals on the real line. Fund. Math., 51:45\u201364, 1962.","journal-title":"Fund. Math."},{"key":"12_CR30","unstructured":"F.\u00a0Maffray and M.\u00a0Preissmann. A translation of Gallai\u2019s paper: \u2018Transitiv orientierbare graphen\u2019. In Perfect Graphs, J.L.R. Alfons\u00edn and B.A. Bruce ed., pages 25\u201366. Wiley, 2001."},{"key":"12_CR31","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"RM McConnell","year":"2003","unstructured":"R.M. McConnell. Linear time recognition of circular-arc graphs. Algorithmica, 37:93\u2013147, 2003.","journal-title":"Algorithmica"},{"key":"12_CR32","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"R.M. McConnell and J.P. Spinrad. Modular decomposition and transitive orientation. Discrete Math., 201:189\u2013241, 1999.","journal-title":"Discrete Math."},{"key":"12_CR33","doi-asserted-by":"publisher","first-page":"160","DOI":"10.4153\/CJM-1971-016-5","volume":"23","author":"A Pnueli","year":"1971","unstructured":"A.\u00a0Pnueli, A.\u00a0Lempel, and A.\u00a0Even. Transitive orientation of graphs and identification of permutation graphs. Canad. J. Math., 23:160\u2013175, 1971.","journal-title":"Canad. J. Math."},{"key":"12_CR34","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"HE Robbins","year":"1939","unstructured":"H.E. Robbins. A theorem on graphs with an application to a problem on traffic control. Amer. Math. Mon., 46:281\u2013283, 1939.","journal-title":"Amer. Math. Mon."},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"F.S. Roberts. Graph Theory and its Applications to Problems of Society. NSF-CMBS Monograph No. 29. SIAM, Philadelphia, PA, 1978.","DOI":"10.1137\/1.9781611970401"},{"key":"12_CR36","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"D.J. Rose, R.E. Tarjan, and G.S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput., 5:266\u2013283, 1976.","journal-title":"SIAM J. Comput."},{"issue":"5","key":"12_CR37","first-page":"129","volume":"1","author":"B Roy","year":"1967","unstructured":"B.\u00a0Roy. Nombre chromatique et plus longs chemins d\u2019un graphe. Rev. Fr. Inf. Rech. Op\u00e9r., 1(5):129\u2013132, 1967.","journal-title":"Rev. Fr. Inf. Rech. Op\u00e9r."},{"issue":"3","key":"12_CR38","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1002\/jgt.3190060307","volume":"6","author":"DJ Skrien","year":"1982","unstructured":"D.J. Skrien. A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular-arc graphs, and nested interval graphs. J. Graph Theory, 6(3):309\u2013316, 1982.","journal-title":"J. Graph Theory"},{"key":"12_CR39","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0095-8956(88)90038-X","volume":"44","author":"J Spinrad","year":"1988","unstructured":"J.\u00a0Spinrad. Circular-arc graphs with clique cover number two. J. Combin. Theory Ser. B, 44:300\u2013306, 1988.","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"12_CR40","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/BF01275674","volume":"11","author":"C Thomassen","year":"1991","unstructured":"C.\u00a0Thomassen. Highly connected non-$$2$$-linked digraphs. Combinatorica, 11(4):393\u2013395, 1991.","journal-title":"Combinatorica"},{"key":"12_CR41","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.jctb.2014.07.004","volume":"110","author":"C Thomassen","year":"2015","unstructured":"C.\u00a0Thomassen. Strongly 2-connected orientations of graphs. J. Combin. Theory Ser. B, 110:67\u201378, 2015.","journal-title":"J. Combin. Theory Ser. B"},{"key":"12_CR42","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0012-365X(76)80011-8","volume":"16","author":"WT Trotter","year":"1976","unstructured":"W.T. Trotter and J.I. Moore. Characterization problems for graphs, partially ordered sets, lattices, and families of sets. Discrete Math., 16:361\u2013381, 1976.","journal-title":"Discrete Math."},{"key":"12_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"AC Tucker","year":"1980","unstructured":"A.C. Tucker. An efficient test for circular arc graphs. SIAM J. Comput., 9:1\u201324, 1980.","journal-title":"SIAM J. Comput."},{"key":"12_CR44","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1090\/S0002-9904-1970-12628-3","volume":"76","author":"AC Tucker","year":"1970","unstructured":"A.C. Tucker. Characterizing circular-arc graphs. Bull. Amer. Math. Soc., 76:1257\u20131260, 1970.","journal-title":"Bull. Amer. Math. Soc."},{"key":"12_CR45","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1137\/0129040","volume":"29","author":"AC Tucker","year":"1975","unstructured":"A.C. Tucker. Colouring a family of circular arcs. SIAM J. Appl. Math., 29:439\u2013502, 1975.","journal-title":"SIAM J. Appl. Math."},{"key":"12_CR46","doi-asserted-by":"publisher","first-page":"535","DOI":"10.2140\/pjm.1971.39.535","volume":"39","author":"AC Tucker","year":"1971","unstructured":"A.C. Tucker. Matrix characterization of circular-arc graphs. Pacific J. Math., 39:535\u2013545, 1971.","journal-title":"Pacific J. Math."},{"key":"12_CR47","first-page":"758","volume":"147","author":"LM Vitaver","year":"1962","unstructured":"L.M. Vitaver. Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix. Dokl. Akad. Nauk SSSR, 147:758\u2013759, 1962.","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["Springer Monographs in Mathematics","Classes of Directed Graphs"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71840-8_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,19]],"date-time":"2019-10-19T16:20:27Z","timestamp":1571502027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-71840-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319718392","9783319718408"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71840-8_12","relation":{},"ISSN":["1439-7382","2196-9922"],"issn-type":[{"type":"print","value":"1439-7382"},{"type":"electronic","value":"2196-9922"}],"subject":[],"published":{"date-parts":[[2018]]}}}