{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:57:58Z","timestamp":1760245078385},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540571551"},{"type":"electronic","value":"9783540479185"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","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":[[1993]]},"DOI":"10.1007\/3-540-57155-8_250","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:05:41Z","timestamp":1330239941000},"page":"222-233","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Deferred-query\u2014An efficient approach for problems on interval and circular-arc graphs"],"prefix":"10.1007","author":[{"given":"Maw-Shang","family":"Chang","sequence":"first","affiliation":[]},{"given":"Sheng-Lung","family":"Peng","sequence":"additional","affiliation":[]},{"given":"Jenn-Liang","family":"Liaw","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0020-0190(90)90064-5","volume":"35","author":"S. R. Arikati","year":"1990","unstructured":"S. Rao Arikati and C. Pandu Rangan, Linear algorithm for optimal path cover problem on interval graphs, Inform. Process. Lett.\n35 (1990), 149\u2013153.","journal-title":"Inform. Process. Lett."},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0020-0190(88)90173-1","volume":"28","author":"A. A. Bertossi","year":"1988","unstructured":"A. A. Bertossi, On the domatic number of interval graphs, Inform. Process. Lett.\n28 (1988) 275\u2013280.","journal-title":"Inform. Process. Lett."},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(81)90048-X","volume":"13","author":"A. A. Bertossi","year":"1981","unstructured":"A. A. Bertossi, The edge Hamiltonian path problem is NP-complete, Inform. Process. Lett.\n13 (1981) 157\u2013159.","journal-title":"Inform. Process. Lett."},{"key":"22_CR4","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(86)90135-3","volume":"23","author":"A. A. Bertossi","year":"1986","unstructured":"A. A. Bertossi and M. A. Bonuccelli, Hamiltonian Circuits in Interval Graph Generalizations, Information Process. Lett.\n23 (1986) 195\u2013200.","journal-title":"Information Process. Lett."},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0020-0190(79)90011-5","volume":"8","author":"M. A. Bonuccelli","year":"1979","unstructured":"M. A. Bonuccelli and D. P. Bovet, Minimum Node Disjoint Path Covering for Circular-Arc Graphs, Information Process. Lett.\n8 (1979) 159\u2013161.","journal-title":"Information Process. Lett."},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. S. Booth","year":"1976","unstructured":"K. S. Booth and G. S. Leuker, Testing for consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms, J. Comput. system Sci.\n13 (1976), 335\u2013379.","journal-title":"J. Comput. system Sci."},{"key":"22_CR7","unstructured":"M. S Chang, O(n) Algorithms for the Hamiltonian Cycle and Node Disjoint Path Cover Problems on Circular-Arc Graphs, Preprint."},{"key":"22_CR8","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1002\/net.3230070305","volume":"7","author":"E. J. Cockayne","year":"1977","unstructured":"E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks\n7 (1977), 247\u2013261.","journal-title":"Networks"},{"key":"22_CR9","unstructured":"M. S. Chang, S. L. Peng and J. L. Liaw, Deferred-Query, An Efficient Approach for Some Problems on Interval Graphs, Preprint."},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0166-218X(84)90061-1","volume":"7","author":"M. Farber","year":"1984","unstructured":"M. Farber, Domination, independent domination, and duality in strongly chordal graphs, Disc. Appl. Math.\n7 (1984), 115\u2013130.","journal-title":"Disc. Appl. Math."},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","volume":"30","author":"H. N. Gabow","year":"1985","unstructured":"H. N. Gabow and R. E. Tarjan, A linear-time algorithm for a special case of disjoint set union, J. Comput. System Sci.\n30 (1985), 209\u2013221.","journal-title":"J. Comput. System Sci."},{"key":"22_CR12","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, CA, 1979."},{"key":"22_CR13","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson and R. E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput.\n5 (1976), 704\u2013714.","journal-title":"SIAM J. Comput."},{"key":"22_CR14","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1016\/0196-6774(88)90023-5","volume":"9","author":"M. C. Golumbic","year":"1988","unstructured":"M. C. Golumbic and P. L. Hammer, Stability in Circular-Arc Graphs, J. of Algorithms\n9 (1988) 314\u2013320.","journal-title":"J. of Algorithms"},{"key":"22_CR16","unstructured":"W. L. Hsu, W. K. Shih and T. C. Chern, An O(n\n2logn) Time Algorithm for the Hamiltonian Cycle Problem, SIAM J. on Compt."},{"key":"22_CR17","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W. L. Hsu","year":"1991","unstructured":"W. L. Hsu and K. H. Tsai, Linear Time Algorithms on Circular-Arc Graphs, Information Process. Lett.\n40 (1991) 123\u2013129.","journal-title":"Information Process. Lett."},{"key":"22_CR18","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"D. S. Johnson, The NP-Complete Column: an Ongoing Guide, J. of Algorithms\n6 (1985) 434\u2013451.","journal-title":"J. of Algorithms"},{"key":"22_CR19","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(85)90050-X","volume":"20","author":"J. M. Keil","year":"1985","unstructured":"J. M. Keil, Finding Hamiltonian Circuits in Interval Graphs, Inform. Process. Lett.\n20 (1985), 201\u2013206.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"22_CR20","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1145\/990518.990521","volume":"7","author":"M. S. Krishnamoorthy","year":"1976","unstructured":"M. S. Krishnamoorthy, An NP-hard problem in a bipartite graphs, SIGACT News\n7 (1), (1976) 26.","journal-title":"SIGACT News"},{"key":"22_CR21","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1137\/0403045","volume":"3","author":"T. L. Lu","year":"1990","unstructured":"T. L. Lu, P. H. Ho and G.J. Chang, The domatic number problem in interval graphs, SIAM J. Disc. Math.\n3. (1990), 531\u2013536.","journal-title":"SIAM J. Disc. Math."},{"key":"22_CR22","unstructured":"G. K. Manacher and T. A. Mankus, Determining the domatic number and a domatic partition of an interval graph in time O(n) given its sorted model, Technique report, Submitted to SIAM J. Disc. Math. 1991."},{"key":"22_CR23","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0020-0190(90)90025-S","volume":"35","author":"G. K. Manacher","year":"1990","unstructured":"G. K. Manacher, T. A. Mankus and C. J. Smith, An Optimum O(nlogn) Algorithm for Finding a Canonical Hamiltonian Path and a Canonical Hamiltonian circuit in a set of intervals, Inform. Process. Lett.\n35 (1990), 205\u2013211.","journal-title":"Inform. Process. Lett."},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1137\/0217003","volume":"17","author":"S. Masuda","year":"1988","unstructured":"S. Masuda and K. Nakajima, An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph, SIAM J. Comput.\n17 (1988) 41\u201352.","journal-title":"SIAM J. Comput."},{"key":"22_CR25","first-page":"114","volume":"III","author":"A. Moitra","year":"1989","unstructured":"A. Moitra and R. C. Johnson, A parallel algorithm for maximum matching on interval graphs, 1989 International Conference on Parallel Processing, III 114\u2013120.","journal-title":"International Conference on Parallel Processing"},{"key":"22_CR26","unstructured":"S. L. Peng and M. S. Chang, A new approach for domatic number problem on interval graphs, Proceedings of National Computer Symposium 1991 R.O.C., 236\u2013241."},{"key":"22_CR27","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970401","volume-title":"Graph theory and its Applications to problems of society","author":"F. S. Roberts","year":"1978","unstructured":"F. S. Roberts, Graph theory and its Applications to problems of society, SIAM, Philadelphia, PA, 1978."},{"key":"22_CR28","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0020-0190(89)90184-1","volume":"33","author":"A. S. Rao","year":"1989","unstructured":"A. Srinivasa Rao and C. Pandu Rangan, Linear algorithm for domatic number problem on interval graphs, Inform. Process. Lett.\n33 (1989), 29\u201333.","journal-title":"Inform. Process. Lett."},{"key":"22_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0209001","volume":"9","author":"A. Tucker","year":"1980","unstructured":"A. Tucker, An Efficient Test for Circular-Arc Graphs, SIAM J. Comput.\n9 (1980) 1\u201324.","journal-title":"SIAM J. Comput."},{"key":"22_CR30","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas Van","year":"1977","unstructured":"P. Van Emde Boas, Preserving order in a forest in less than logarithmic time and linear space, Inform. Process. Lett.\n6 (1977), 80\u201382.","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57155-8_250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T21:13:08Z","timestamp":1578517988000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57155-8_250"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540571551","9783540479185"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-57155-8_250","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"9 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}