{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:10:59Z","timestamp":1725541859644},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_11","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T08:12:27Z","timestamp":1259827947000},"page":"122-132","source":"Crossref","is-referenced-by-count":1,"title":["Sub-coloring and Hypo-coloring Interval Graphs"],"prefix":"10.1007","author":[{"given":"Rajiv","family":"Gandhi","sequence":"first","affiliation":[]},{"suffix":"Jr.","given":"Bradford","family":"Greening","sequence":"additional","affiliation":[]},{"given":"Sriram","family":"Pemmaraju","sequence":"additional","affiliation":[]},{"given":"Rajiv","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D.: The complexity of g-free colorability. Discrete Math, 21\u201330 (1997)","DOI":"10.1016\/S0012-365X(97)84217-3"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0012-365X(89)90196-9","volume":"74","author":"M.O. Albertson","year":"1989","unstructured":"Albertson, M.O., Jamison, R.E., Hedetnieme, S.T., Locke, S.C.: The subchromatic number of a graph. Discrete Math.\u00a074, 33\u201349 (1989)","journal-title":"Discrete Math."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"11_CR4","unstructured":"Broere, I., Mynhardt, C.M.: Generalized colorings of outerplanar and planar graphs. In: Proceedings of the 10th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 151\u2013161 (1984)"},{"key":"11_CR5","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s00607-002-1461-1","volume":"69","author":"H. Broersma","year":"2002","unstructured":"Broersma, H., Fomin, F.V., Nesetril, J., Woeginger, G.J.: More about subcolorings. Computing\u00a069, 187\u2013203 (2002)","journal-title":"Computing"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.dam.2004.06.016","volume":"146","author":"D. deWerra","year":"2005","unstructured":"deWerra, D., Demange, M., Monnot, J., Paschos, V.T.: A hypocoloring model for batch scheduling. Discrete Applied Mathematics\u00a0146, 3\u201325 (2005)","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Elbassioni, K.M., Raman, R., Ray, S., Sitters, R.: On the approximability of the maximum feasible subsystem problem with 0\/1-coefficients. In: Proceedings of the 20th ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 1210\u20131219 (2009)","DOI":"10.1137\/1.9781611973068.131"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"635","DOI":"10.1137\/S0895480101395245","volume":"16","author":"J. Fiala","year":"2003","unstructured":"Fiala, J., Jansen, K., Le, V.B., Seidel, E.: Graph subcoloring:complexity and algorithms. SIAM Journal on Discrete Mathematics\u00a016, 635\u2013650 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Gardi, F.: On partitioning interval and circular-arc graphs into proper interval subgraphs with applications. In: Latin American Theoretical Informatics Symposium (LATIN), pp. 129\u2013140 (2004)","DOI":"10.1007\/978-3-540-24698-5_17"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1137\/0601025","volume":"1","author":"M.R. Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S., Miller, G.L., Papadimitriou, C.H.: The complexity of coloring circular arcs and chords. SIAM J. Algebraic and Discrete Methods\u00a01, 216\u2013227 (1980)","journal-title":"SIAM J. Algebraic and Discrete Methods"},{"key":"11_CR11","unstructured":"Hartman, C.: Extremal Problems in Graph Theory (1997)"},{"key":"11_CR12","first-page":"60","volume-title":"Proceedings of the 24th Annual ACM symposium on Principles of Distributed Computing (PODC)","author":"K. Fabian","year":"2005","unstructured":"Fabian, K., Thomas, M., Roger, W.: On the locality of bounded growth. In: Proceedings of the 24th Annual ACM symposium on Principles of Distributed Computing (PODC), pp. 60\u201368. ACM, New York (2005)"},{"issue":"4","key":"11_CR13","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1016\/j.orl.2004.07.006","volume":"33","author":"D. Marx","year":"2005","unstructured":"Marx, D.: A short proof of the NP-completeness of minimum sum interval coloring. Operations Research Letters\u00a033(4), 382\u2013384 (2005)","journal-title":"Operations Research Letters"},{"issue":"2","key":"11_CR14","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R.M. McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica\u00a037(2), 93\u2013147 (2003)","journal-title":"Algorithmica"},{"issue":"6","key":"11_CR15","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1109\/71.932708","volume":"12","author":"A.W. Mu\u2019alem","year":"2001","unstructured":"Mu\u2019alem, A.W., Feitelson, D.G.: Utilization, predictability, workloads, and user runtime estimates in scheduling the ibm sp2 with backfilling. IEEE Trans. Parallel and Distributed Syst.\u00a012(6), 529\u2013543 (2001)","journal-title":"IEEE Trans. Parallel and Distributed Syst."},{"key":"11_CR16","unstructured":"Mynhardt, C.M., Broere, I.: Generalized colorings of graphs. In: Proceedings of the 11th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pp. 583\u2013594 (1985)"},{"issue":"2","key":"11_CR17","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A. Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms\u00a020(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/978-3-540-75520-3_29","volume-title":"Algorithms \u2013 ESA 2007","author":"S.V. Pemmaraju","year":"2007","unstructured":"Pemmaraju, S.V., Pirwani, I.A.: Good quality virtual realization of unit ball graphs. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 311\u2013322. Springer, Heidelberg (2007)"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1007\/11523468_86","volume-title":"Automata, Languages and Programming","author":"S.V. Pemmaraju","year":"2005","unstructured":"Pemmaraju, S.V., Raman, R.: Approximation algorithms for the max-coloring problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1064\u20131075. Springer, Heidelberg (2005)"},{"key":"11_CR20","unstructured":"Pemmaraju, S.V., Raman, R., Varadarajan, K.: Buffer minimization using max-coloring. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 562\u2013571 (2004)"},{"issue":"9","key":"11_CR21","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1016\/j.jpdc.2005.05.003","volume":"65","author":"E. Shmueli","year":"1995","unstructured":"Shmueli, E., Feitelson, D.G.: Backfilling with look ahead to optimize the packing of parallel jobs. J. Parallel and Distributed Computing\u00a065(9), 1090\u20131107 (1995)","journal-title":"J. Parallel and Distributed Computing"},{"key":"11_CR22","unstructured":"Stacho, J.: Complexity of Generalized Colourings of Chordal Graphs (2008)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11409-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T11:27:19Z","timestamp":1580297239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}