{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:56:28Z","timestamp":1742964988677,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030604394"},{"type":"electronic","value":"9783030604400"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-60440-0_24","type":"book-chapter","created":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T09:03:18Z","timestamp":1602752598000},"page":"298-309","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterization and Linear-Time Recognition of Paired Threshold Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6927-438X","authenticated-orcid":false,"given":"Yixin","family":"Cao","sequence":"first","affiliation":[]},{"given":"Guozhen","family":"Rong","sequence":"additional","affiliation":[]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,9]]},"reference":[{"key":"24_CR1","doi-asserted-by":"publisher","unstructured":"Chv\u00e1tal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. In: Hammer, P.L., Johnson, E.L., Korte, B.H., Nemhauser, G.L. (eds.) Annals of Discrete Mathematics. Studies in Integer Programming, vol. 1, pp. 145\u2013162. Elsevier (1977). https:\/\/doi.org\/10.1016\/S0167-5060(08)70731-3","DOI":"10.1016\/S0167-5060(08)70731-3"},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","volume":"138","author":"DG Corneil","year":"2004","unstructured":"Corneil, D.G.: A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs. Discret. Appl. Math. 138(3), 371\u2013379 (2004). https:\/\/doi.org\/10.1016\/j.dam.2003.07.001","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"24_CR3","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1137\/S0097539792269095","volume":"25","author":"X Deng","year":"1996","unstructured":"Deng, X., Hell, P., Huang, J.: Linear-time representation algorithms for proper circular-Arc graphs and proper interval graphs. SIAM J. Comput. 25(2), 390\u2013403 (1996). https:\/\/doi.org\/10.1137\/S0097539792269095","journal-title":"SIAM J. Comput."},{"key":"24_CR4","unstructured":"Foldes, S., Hammer, P.L.: Split graphs. In: Proceedings of the 8th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. XIX, pp. 311\u2013315 (1977)"},{"key":"24_CR5","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"PC Gilmore","year":"1964","unstructured":"Gilmore, P.C., Hoffman, A.J.: A characterization of comparability graphs and of interval graphs. Can. J. Math. 16, 539\u2013548 (1964). https:\/\/doi.org\/10.4153\/CJM-1964-055-5","journal-title":"Can. J. Math."},{"issue":"1","key":"24_CR6","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","volume":"28","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Peled, U.N., Sun, X.: Difference graphs. Discret. Appl. Math. 28(1), 35\u201344 (1990). https:\/\/doi.org\/10.1016\/0166-218X(90)90092-Q","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"24_CR7","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/S0097539792224814","volume":"28","author":"WL Hsu","year":"1999","unstructured":"Hsu, W.L., Ma, T.H.: Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM J. Comput. 28(3), 1004\u20131020 (1999). https:\/\/doi.org\/10.1137\/S0097539792224814","journal-title":"SIAM J. Comput."},{"key":"24_CR8","doi-asserted-by":"publisher","unstructured":"Klav\u00edk, P., Otachi, Y., Sejnoha, J.: On the classes of interval graphs of limited nesting and count of lengths. In: Hong, S. (ed.) ISAAC 2016. LIPIcs, vol. 64, pp. 45:1\u201345:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.45","DOI":"10.4230\/LIPIcs.ISAAC.2016.45"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Okamoto, Y., Otachi, Y., Uno, Y.: Linear-time recognition of double-threshold graphs (2020, this volume)","DOI":"10.1007\/978-3-030-60440-0_23"},{"key":"24_CR10","unstructured":"Leibowitz, R.: Interval Counts and Threshold Numbers of Graphs. Ph.D. thesis, Rutgers University, New Brunswick, New Jersey (1978)"},{"issue":"7","key":"24_CR11","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0898-1221(93)90308-I","volume":"25","author":"PJ Looges","year":"1993","unstructured":"Looges, P.J., Olariu, S.: Optimal greedy algorithms for indifference graphs. Comput. Math. Appl. 25(7), 15\u201325 (1993). https:\/\/doi.org\/10.1016\/0898-1221(93)90308-I","journal-title":"Comput. Math. Appl."},{"key":"24_CR12","doi-asserted-by":"publisher","unstructured":"Mahadev, N.V., Peled, U.N.: Threshold graphs and related topics. In: Annals of Discrete Mathematics, vol. 56. North-Holland Publishing Co., Amsterdam, The Netherlands (1995). https:\/\/doi.org\/10.1016\/S0167-5060(06)80001-4","DOI":"10.1016\/S0167-5060(06)80001-4"},{"issue":"3\u20134","key":"24_CR13","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0020-0190(00)00041-7","volume":"74","author":"SD Nikolopoulos","year":"2000","unstructured":"Nikolopoulos, S.D.: Recognizing cographs and threshold graphs through a classification of their edges. Inf. Proc. Lett. 74(3\u20134), 129\u2013139 (2000). https:\/\/doi.org\/10.1016\/S0020-0190(00)00041-7","journal-title":"Inf. Proc. Lett."},{"issue":"5","key":"24_CR14","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0020-0190(88)90091-9","volume":"27","author":"G Ramalingam","year":"1988","unstructured":"Ramalingam, G., Rangan, C.P.: A unified approach to domination problems on interval graphs. Inf. Proc. Lett. 27(5), 271\u2013274 (1988). https:\/\/doi.org\/10.1016\/0020-0190(88)90091-9","journal-title":"Inf. Proc. Lett."},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/j.dam.2018.05.008","volume":"250","author":"V Ravanmehr","year":"2018","unstructured":"Ravanmehr, V., Puleo, G.J., Bolouki, S., Milenkovic, O.: Paired threshold graphs. Discret. Appl. Math. 250, 291\u2013308 (2018). https:\/\/doi.org\/10.1016\/j.dam.2018.05.008","journal-title":"Discret. Appl. Math."},{"key":"24_CR16","unstructured":"Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory (Proceedings of the 2nd Ann Arbor Graph Theory Conference 1968), pp. 139\u2013146. Academic Press, New York (1969)"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1090\/S0002-9939-1962-0172273-0","volume":"13","author":"ES Wolk","year":"1962","unstructured":"Wolk, E.S.: The comparability graph of a tree. P. Amer. Math. Soc. 13, 789\u2013795 (1962). https:\/\/doi.org\/10.1090\/S0002-9939-1962-0172273-0","journal-title":"P. Amer. Math. Soc."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-60440-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T18:02:06Z","timestamp":1710266526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-60440-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030604394","9783030604400"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-60440-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"9 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Leeds","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 June 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 June 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"46","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algorithms.leeds.ac.uk\/wg2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"94","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.7","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}