{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:14:53Z","timestamp":1725459293530},"publisher-location":"Berlin\/Heidelberg","reference-count":20,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540555536"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0035179","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T15:20:01Z","timestamp":1138202401000},"page":"207-220","source":"Crossref","is-referenced-by-count":2,"title":["Optimal k-colouring and k-nesting of intervals"],"prefix":"10.1007","author":[{"given":"Irith Ben-Arroyo","family":"Hartman","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"19_CR1","doi-asserted-by":"crossref","first-page":"249","DOI":"10.2140\/pjm.1985.118.249","volume":"118","author":"R. Aharoni","year":"1985","unstructured":"R. Aharoni, I.B-A. Hartman, and A.J. Hoffman, Path Partitions and Packs of Acyclic Digraphs, Pacific Journal of Mathematics, 118(2) (1985), 249\u2013259.","journal-title":"Pacific Journal of Mathematics"},{"issue":"7","key":"19_CR2","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/43.31531","volume":"8","author":"R. Bar-Yehuda","year":"1989","unstructured":"R. Bar-Yehuda, J.A. Feldman, R.Y. Pinter, and S. Wimer, Depth First Search and Dynamic Programming Algorithms for Efficient CMOS Cell Generation IEEE Trans. on CAD, 8(7), (1989), 737\u2013743.","journal-title":"IEEE Trans. on CAD"},{"key":"19_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J.A. Bondy","year":"1976","unstructured":"J.A. Bondy and U.S.R. Murty, Graph Theory with Applications Macmillan, London, and American Elsevier, New York 1976."},{"key":"19_CR4","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1080\/00207169008803871","volume":"34","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner, M. Overmars, and E. Welzl, I.B-A. Hartman, and J.A. Feldman, Ranking Intervals Under Visibility Constraints, Intern. J.Computer Math. 34, (1990), 129\u2013144.","journal-title":"Intern. J.Computer Math."},{"unstructured":"S. Even, Graph Algorithms, Computer Science Press, 1979.","key":"19_CR5"},{"key":"19_CR6","first-page":"811","volume":"286A","author":"J.C. Fournier","year":"1978","unstructured":"J.C. Fournier, Une Characterization des graphes de cordes, C.R.Acad.Sci.Paris 286A, (1978), 811\u2013813.","journal-title":"C.R.Acad.Sci.Paris"},{"key":"19_CR7","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1002\/net.3230030305","volume":"3","author":"F. Gavril","year":"1973","unstructured":"F. Gavril, Algorithms for a maximum clique and a minimum independent set of a circle graph, Networks 3, (1973), 261\u2013273.","journal-title":"Networks"},{"doi-asserted-by":"crossref","unstructured":"M.C.Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980.","key":"19_CR8","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"doi-asserted-by":"crossref","unstructured":"A.Hashimoto and J.Stevens, Wire Routing by Optimizing Channel Assignment, Proc. 8th DA Conference, (1971), 214\u2013224.","key":"19_CR9","DOI":"10.1145\/800158.805069"},{"key":"19_CR10","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/0097-3165(83)90046-8","volume":"34","author":"A.J. Hoffman","year":"1983","unstructured":"A.J. Hoffman, Extending Greene's Theorem to Directed Graphs, J. Combinatorial Theory, Ser.A, 34 (1983), 102\u2013107.","journal-title":"J. Combinatorial Theory, Ser.A"},{"key":"19_CR11","first-page":"223","volume":"8","author":"A.J. Hoffman","year":"1956","unstructured":"A.J. Hoffman and J.B. Kruskal, Integral boundary points of convex polyhedra, in Linear inequalities and related systems, Annals of Mathematics Study 8, (1956), 223\u2013246.","journal-title":"Linear inequalities and related systems, Annals of Mathematics Study"},{"issue":"no.5","key":"19_CR12","first-page":"1093","volume":"244","author":"L.G. Khachian","year":"1979","unstructured":"L.G. Khachian, A Polynomial algorithm for linear programming, Doclady Akad. Nauk USSR, 244, no.5 7 (1979), 1093\u201396.","journal-title":"Doclady Akad. Nauk USSR"},{"doi-asserted-by":"crossref","unstructured":"A.S.LaPaugh and R.Y.Pinter, Channel Routing for Integrated Circuits, Annual Review of Computer Science 4, (1989).","key":"19_CR13","DOI":"10.1146\/annurev.cs.04.060190.001515"},{"key":"19_CR14","first-page":"39","volume":"7","author":"L. Redei","year":"1934","unstructured":"L. Redei, Ein Kombinatorischer Satz, Acta Litt. Sci. Szeged 7 (1934), 39\u201343.","journal-title":"Acta Litt. Sci. Szeged"},{"key":"19_CR15","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1109\/TCAD.1985.1270096","volume":"CAD-4","author":"T.G. Szymanski","year":"1985","unstructured":"T.G. Szymanski, Dogleg Channel Routing is NP-Completc, IEEE Trans. on Computer-Aided Design CAD-4, (Jan. 1985), 31\u201341.","journal-title":"IEEE Trans. on Computer-Aided Design"},{"key":"19_CR16","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1109\/TC.1981.1675787","volume":"C-30","author":"T. Uehara","year":"1981","unstructured":"T. Uehara and W. M. vanCleemput, Optimal Layout of CMOS Functional Arrays, IEEE Trans. on Comput., C-30, (1981), 305\u2013312.","journal-title":"IEEE Trans. on Comput."},{"key":"19_CR17","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1109\/TCAD.1987.1270322","volume":"CAD-6","author":"S. Wimer","year":"1987","unstructured":"S. Wimer, R. Y. Pinter, and J. A. Feldman, Optimal Chaining of CMOS Transistors in a Functional Cell, IEEE Trans. on CAD of Integrated Circuits and Systems, CAD-6, (1987), 795\u2013801.","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"},{"issue":"2","key":"19_CR18","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1109\/43.68409","volume":"CAD-10","author":"U. Yoeli","year":"1991","unstructured":"U. Yoeli, A Robust Channel Router, IEEE Trans. on Computer-Aided Design CAD-10(2), (February 1991), 212\u2013219.","journal-title":"IEEE Trans. on Computer-Aided Design"},{"doi-asserted-by":"crossref","unstructured":"T.Yoshimura, An Efficient Channel Router, Proc. 21st Design Automation Conference, (June 1984), 38\u201344.","key":"19_CR19","DOI":"10.1109\/DAC.1984.1585770"},{"issue":"1","key":"19_CR20","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1109\/TCAD.1982.1269993","volume":"CAD-1","author":"T. Yoshimura","year":"1982","unstructured":"T. Yoshimura and E.S. Kuh, Efficient Algorithms for Channel Routing, IEEE Trans. on Computer-Aided Design, CAD-1(1), (Jan. 1982), 25\u201335.","journal-title":"IEEE Trans. on Computer-Aided Design"}],"container-title":["Lecture Notes in Computer Science","Theory of Computing and Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0035179.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T22:13:20Z","timestamp":1607552000000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0035179"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540555536"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0035179","relation":{},"subject":[]}}