{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T09:46:01Z","timestamp":1649065561226},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,2,28]],"date-time":"2012-02-28T00:00:00Z","timestamp":1330387200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2012,2,28]],"date-time":"2012-02-28T00:00:00Z","timestamp":1330387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2012,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The graph sandwich problem for property \u03a0 is defined as follows: Given two graphs <jats:italic>G<\/jats:italic>\n            <jats:sub>1<\/jats:sub>=(<jats:italic>V<\/jats:italic>,<jats:italic>E<\/jats:italic>\n            <jats:sub>1<\/jats:sub>) and <jats:italic>G<\/jats:italic>\n            <jats:sub>2<\/jats:sub>=(<jats:italic>V<\/jats:italic>,<jats:italic>E<\/jats:italic>\n            <jats:sub>2<\/jats:sub>) such that <jats:italic>E<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\u2286<jats:italic>E<\/jats:italic>\n            <jats:sub>2<\/jats:sub>, is there a graph <jats:italic>G<\/jats:italic>=(<jats:italic>V<\/jats:italic>,<jats:italic>E<\/jats:italic>) such that <jats:italic>E<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\u2286<jats:italic>E<\/jats:italic>\u2286<jats:italic>E<\/jats:italic>\n            <jats:sub>2<\/jats:sub> which satisfies property \u03a0? We propose to study sandwich problems for properties \u03a0 concerning orientations, such as Eulerian orientation of a mixed graph and orientation with given in-degrees of a graph. We present a characterization and a polynomial-time algorithm for solving the <jats:italic>m<\/jats:italic>-orientation sandwich problem.<\/jats:p>","DOI":"10.1007\/s13173-012-0065-7","type":"journal-article","created":{"date-parts":[[2012,2,27]],"date-time":"2012-02-27T09:20:57Z","timestamp":1330334457000},"page":"85-93","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Sandwich problems on orientations"],"prefix":"10.1007","volume":"18","author":[{"given":"Olivier","family":"Durand\u00a0de\u00a0Gevigney","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sulamita","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Viet-Hang","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zolt\u00e1n","family":"Szigeti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,2,28]]},"reference":[{"key":"65_CR1","doi-asserted-by":"publisher","first-page":"3664","DOI":"10.1016\/j.disc.2008.01.014","volume":"309","author":"S Dantas","year":"2009","unstructured":"Dantas S, Klein S, Mello CP, Morgana A (2009) The graph sandwich problem for P4-sparse graphs. Discrete Math 309:3664\u20133673","journal-title":"Discrete Math"},{"key":"65_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/s10479-010-0792-0","volume":"188","author":"S Dantas","year":"2011","unstructured":"Dantas S, Figueiredo CMH, Golumbic MC, Klein S, Maffray F (2011) The chain graph sandwich problem. Ann Oper Res 188:133\u2013139","journal-title":"Ann Oper Res"},{"key":"65_CR3","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/BF03192551","volume":"14","author":"M Dourado","year":"2008","unstructured":"Dourado M, Petito P, Teixeira RB, Figueiredo CMH (2008) Helly property, clique graphs, complementary graph classes, and sandwich problems. J Braz Comput Soc 14:45\u201352","journal-title":"J Braz Comput Soc"},{"key":"65_CR4","first-page":"39","volume":"4","author":"J Edmonds","year":"1977","unstructured":"Edmonds J (1977) Matroid intersection. Discrete Optim 4:39\u201349 (Proc Adv Res Inst Discrete Optimization and Systems Appl, Banff, Alta)","journal-title":"Discrete Optim"},{"key":"65_CR5","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J Edmonds","year":"1973","unstructured":"Edmonds J, EL Johnson (1973) Matching, Euler tours and the Chinese postman. Math Program 5:88\u2013124","journal-title":"Math Program"},{"key":"65_CR6","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S Even","year":"1976","unstructured":"Even S, Itai A, Shamir A (1976) On the complexity of timetable and multicommodity flow problems. SIAM J Comput 5:691\u2013703","journal-title":"SIAM J Comput"},{"key":"65_CR7","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2007.04.007","volume":"38","author":"CMH Figueiredo","year":"2007","unstructured":"Figueiredo CMH, Faria L, Klein S, Sritharan R (2007) On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs. Theor Comput Sci 38:57\u201367","journal-title":"Theor Comput Sci"},{"key":"65_CR8","volume-title":"Flows in Networks","author":"LR Ford","year":"1962","unstructured":"Ford LR, Fulkerson DR (1962) Flows in Networks. Princeton University Press, Princeton"},{"key":"65_CR9","first-page":"97","volume":"16","author":"A Frank","year":"1982","unstructured":"Frank A (1982) An algorithm for submodular functions on graphs. Ann Discrete Math 16:97\u2013120","journal-title":"Ann Discrete Math"},{"key":"65_CR10","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"},{"issue":"3","key":"65_CR11","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A Frank","year":"1988","unstructured":"Frank A, Tardos E (1988) Generalized polymatroids and submodular flows. Submodular optimization. Math Program 42(3):489\u2013563","journal-title":"Math Program"},{"issue":"3","key":"65_CR12","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"MC Golumbic","year":"1995","unstructured":"Golumbic MC, Kaplan H, Shamir R (1995) Graph sandwich problems. J Algorithms 19(3):449\u2013473","journal-title":"J Algorithms"},{"issue":"4","key":"65_CR13","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/0016-0032(65)90340-6","volume":"279","author":"SL Hakimi","year":"1965","unstructured":"Hakimi SL (1965) On the degrees of the vertices of a directed graph. J Franklin Inst 279(4):290\u2013308","journal-title":"J Franklin Inst"},{"key":"65_CR14","first-page":"217","volume-title":"Proceedings of IARCS annual conference on foundations of software technology and theoretical computer science","author":"P Heggernes","year":"2011","unstructured":"Heggernes P, van\u2019t Hof P, Lokshtanov D, Paul C (2011) Obtaining a bipartite graph by contracting few edges. In: Proceedings of IARCS annual conference on foundations of software technology and theoretical computer science, pp 217\u2013228"},{"key":"65_CR15","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1090\/psapm\/010\/0114759","volume":"10","author":"AJ Hoffman","year":"1960","unstructured":"Hoffman AJ (1960) Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Proc Symp Appl Math 10:113\u2013127","journal-title":"Proc Symp Appl Math"},{"issue":"4","key":"65_CR16","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer I (1981) The NP-completeness of edge-coloring. SIAM J Comput 10(4):718\u2013720","journal-title":"SIAM J Comput"},{"issue":"4","key":"65_CR17","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J\u00a0ACM 48(4):761\u2013777","journal-title":"J\u00a0ACM"},{"key":"65_CR18","volume-title":"Matroid theory","author":"JG Oxley","year":"1992","unstructured":"Oxley JG (1992) Matroid theory. Oxford University Press, New York"},{"issue":"1","key":"65_CR19","first-page":"35","volume":"1","author":"D P\u00e1lv\u00f6lgyi","year":"2009","unstructured":"P\u00e1lv\u00f6lgyi D (2009) Deciding soccer scores and partial orientations of graphs. Acta Univ Sapientiae, Math 1(1):35\u201342","journal-title":"Acta Univ Sapientiae, Math"},{"key":"65_CR20","series-title":"Algorithms and combinatorics","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Algorithms and combinatorics, vol 24. Springer, Berlin"},{"issue":"2","key":"65_CR21","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J Comb Theory, Ser B 80(2):346\u2013355","journal-title":"J Comb Theory, Ser B"},{"key":"65_CR22","doi-asserted-by":"publisher","first-page":"2581","DOI":"10.1016\/j.disc.2007.06.004","volume":"308","author":"R Sritharan","year":"2008","unstructured":"Sritharan R (2008) Chordal bipartite completion of colored graphs. Discrete Math 308:2581\u20132588","journal-title":"Discrete Math"},{"issue":"3","key":"65_CR23","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579369","volume":"5","author":"E Tardos","year":"1985","unstructured":"Tardos E (1985) A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3):247\u2013255","journal-title":"Combinatorica"},{"key":"65_CR24","doi-asserted-by":"publisher","first-page":"1286","DOI":"10.1016\/j.dam.2009.12.002","volume":"158","author":"RB Teixeira","year":"2010","unstructured":"Teixeira RB, Dantas S, Figueiredo CMH (2010) The polynomial dichotomy for three nonempty part sandwich problems. Discrete Appl Math 158:1286\u20131304","journal-title":"Discrete Appl Math"},{"key":"65_CR25","doi-asserted-by":"publisher","first-page":"314","DOI":"10.4153\/CJM-1952-028-2","volume":"4","author":"WT Tutte","year":"1952","unstructured":"Tutte WT (1952) The factors of graphs. Can J Math 4:314\u2013328","journal-title":"Can J Math"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0065-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-012-0065-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0065-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0065-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T18:11:11Z","timestamp":1630519871000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-012-0065-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,28]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["65"],"URL":"https:\/\/doi.org\/10.1007\/s13173-012-0065-7","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,28]]},"assertion":[{"value":"1 February 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}