{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T06:56:13Z","timestamp":1648882573849},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p> In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as \"subroutines\" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a \"forbidden subgraph\" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it. <\/jats:p>","DOI":"10.1142\/s1793830910000693","type":"journal-article","created":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T08:44:00Z","timestamp":1286873040000},"page":"331-345","source":"Crossref","is-referenced-by-count":1,"title":["SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS"],"prefix":"10.1142","volume":"02","author":[{"given":"RAJIV","family":"GANDHI","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University-Camden, Camden, NJ 08102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"suffix":"Jr.","given":"BRADFORD","family":"GREENING","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rutgers University-Camden, Camden, NJ 08102, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SRIRAM","family":"PEMMARAJU","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Iowa, Iowa City, IA 52242, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"RAJIV","family":"RAMAN","sequence":"additional","affiliation":[{"name":"Max-Planck Institute for Informatik, Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,5]]},"reference":[{"key":"rf1","first-page":"21","author":"Achlioptas D.","journal-title":"Discrete Math."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(89)90196-9"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-002-1461-1"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.06.016"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480101395245"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1137\/0601025"},{"key":"rf13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf14","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic M. C.","year":"1980"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2004.07.006"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1032-7"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1109\/71.932708"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.05.003"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T01:34:42Z","timestamp":1565141682000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":13,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,4,5]]},"published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1142\/S1793830910000693"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000693","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}