{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:15:52Z","timestamp":1725664552025},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_76","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:52:56Z","timestamp":1330278776000},"page":"358-368","source":"Crossref","is-referenced-by-count":3,"title":["Computing a dominating pair in an asteroidal triple-free graph in linear time"],"prefix":"10.1007","author":[{"given":"Derek G.","family":"Corneil","sequence":"first","affiliation":[]},{"given":"Stephan","family":"Olariu","sequence":"additional","affiliation":[]},{"given":"Lorna","family":"Stewart","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"31_CR1","volume-title":"Data Structures and Algorithms","author":"A. V. Aho","year":"1983","unstructured":"A. V. Aho, J. E. Hopcroft and J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, Reading, Massachusetts, 1983."},{"key":"31_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1002\/net.3230020103","volume":"2","author":"K. A. Baker","year":"1971","unstructured":"K. A. Baker, P. C. Fishburn and F. S. Roberts, Partial orders of dimension two, Networks, 2, (1971), 11\u201328.","journal-title":"Networks"},{"key":"31_CR3","first-page":"131","volume-title":"LNCS, Vol. 709","author":"H. Balakrishnan","year":"1993","unstructured":"H. Balakrishnan, A. Rajaraman and C. Pandu Rangan, Connected domination and Steiner set on asteroidal triple-free graphs, Proc. Workshop on Algorithms and Data Structures, WADS'93, Montreal, Canada, August 1993, LNCS, Vol. 709, F. Dehne, J.-R. Sack, N. Santoro, S. Whitesides (Eds.), Springer-Verlag, Heidelberg, Berlin, 1993, 131\u2013141."},{"key":"31_CR4","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, North-Holland, Amsterdam, 1976."},{"key":"31_CR5","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. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms. Journal of Comput. Syst. Sci., 13 (1976), 335\u2013379.","journal-title":"Journal of Comput. Syst. Sci."},{"key":"31_CR6","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1145\/322123.322125","volume":"26","author":"K. S. Booth","year":"1979","unstructured":"K. S. Booth and G. S. Lueker, A linear time algorithm for deciding interval graph isomorphism, Journal of the ACM, 26 (1979), 183\u2013195.","journal-title":"Journal of the ACM"},{"key":"31_CR7","unstructured":"F. Cheah, A recognition algorithm for II-graphs, Doctoral thesis, Department of Computer Science, University of Toronto, (available as TR 246\/90), 1990."},{"key":"31_CR8","unstructured":"D.G. Corneil and P.A. Kamula Extensions of permutation and interval graphs, Proceedings 18th Southeastern Conference on Combinatorics, Graph Theory and Computing (1987), 267\u2013276."},{"key":"31_CR9","first-page":"211","volume-title":"LNCS, Vol. 790","author":"D.G. Corneil","year":"1994","unstructured":"D.G. Corneil, S. Olariu and L. Stewart, Asteroidal triple-free graphs, Proc. 19th International Workshop on Graph Theoretic Concepts in Computer Science, WG'93, Utrecht, The Netherlands, June 1993, LNCS, Vol. 790, J. van Leeuwen (Ed.), Springer-Verlag, Berlin, 1994, 211\u2013224."},{"key":"31_CR10","doi-asserted-by":"crossref","unstructured":"D.G. Corneil, S. Olariu and L. Stewart, A linear time algorithm to compute a dominating path in an AT-free graph, Information Processing Letters, to appear.","DOI":"10.1016\/0020-0190(95)00021-4"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"D.G. Corneil, S. Olariu and L. Stewart, Asteroidal triple-free graphs, Technical Report TR-94-31, Department of Computer Science, Old Dominion University, November, 1994.","DOI":"10.1007\/3-540-57899-4_54"},{"key":"31_CR12","doi-asserted-by":"crossref","unstructured":"D.G. Corneil, S. Olariu and L. Stewart, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, submitted for publication, (available as TR 294\/95, Department of Computer Science, University of Toronto), extended abstract to appear in Proceedings of ICALP Conference, July 1995.","DOI":"10.1007\/3-540-60084-1_82"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(88)90032-7","volume":"21","author":"I. Dagan","year":"1988","unstructured":"I. Dagan, M.C. Golumbic and R.Y. Pinter, Trapezoid graphs and their coloring, Discrete Applied Mathematics 21 (1988), 35\u201346.","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1145\/321707.321710","volume":"19","author":"S. Even","year":"1972","unstructured":"S. Even, A. Pnueli and A. Lempel, Permutation graphs and transitive graphs, Journal of the ACM 19 (1972), 400\u2013410.","journal-title":"Journal of the ACM"},{"key":"31_CR15","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":"31_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(84)90016-7","volume":"9","author":"M.C. Golumbic","year":"1984","unstructured":"M.C. Golumbic, C.L. Monma and W.T. Trotter Jr., Tolerance graphs, Discrete Applied Mathematics 9 (1984), 157\u2013170.","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR17","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0406032","volume":"6","author":"D. Kratsch","year":"1993","unstructured":"D. Kratsch and L. Stewart, Domination on cocomparability graphs, SIAM Journal on Discrete Mathematics, 6 (1993) 400\u2013417.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"31_CR18","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C.G. Lekkerkerker","year":"1962","unstructured":"C.G. Lekkerkerker and J.C. Boland, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae 51 (1962), 45\u201364.","journal-title":"Fundamenta Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_76.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:56:13Z","timestamp":1605646573000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_76","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}