{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:58:27Z","timestamp":1762102707092,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["KAKENHI JP18H05291","JP20H05795"],"award-info":[{"award-number":["KAKENHI JP18H05291","JP20H05795"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20K11692","JP20K20417"],"award-info":[{"award-number":["JP20K11692","JP20K20417"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["KAKENHI JP20H05795","JP20K11670"],"award-info":[{"award-number":["KAKENHI JP20H05795","JP20K11670"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003382","name":"Core Research for Evolutional Science and Technology","doi-asserted-by":"publisher","award":["JPMJCR1402","JPMJCR1402"],"award-info":[{"award-number":["JPMJCR1402","JPMJCR1402"]}],"id":[{"id":"10.13039\/501100003382","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["KAKENHI JP18H04091","JP18K11168"],"award-info":[{"award-number":["KAKENHI JP18H04091","JP18K11168"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18K11169","JP20H05793"],"award-info":[{"award-number":["JP18K11169","JP20H05793"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["KAKENHI JP17K00017","JP20H05964"],"award-info":[{"award-number":["KAKENHI JP17K00017","JP20H05964"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G = (V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a <jats:italic>double-threshold graph<\/jats:italic> if there exist a vertex-weight function <jats:inline-formula><jats:alternatives><jats:tex-math>$$w :V \\rightarrow \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>w<\/mml:mi>\n                    <mml:mo>:<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>\u2192<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and two real numbers <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathtt {lb}, \\mathtt {ub}\\in \\mathbb {R}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>lb<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>ub<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>R<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$uv \\in E$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>u<\/mml:mi>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if and only if <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathtt {lb}\\le \\mathtt {w}(u) + \\mathtt {w}(v) \\le \\mathtt {ub}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>lb<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>w<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>u<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>w<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>v<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>ub<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In the literature, those graphs are studied also as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs that relates them to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi\u00a0[Algorithmica 2020] ran in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{3} m)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where <jats:italic>n<\/jats:italic> and <jats:italic>m<\/jats:italic> are the numbers of vertices and edges, respectively.<\/jats:p>","DOI":"10.1007\/s00453-021-00921-9","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T07:02:48Z","timestamp":1641452568000},"page":"1163-1181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Linear-Time Recognition of Double-Threshold Graphs"],"prefix":"10.1007","volume":"84","author":[{"given":"Yusuke","family":"Kobayashi","sequence":"first","affiliation":[]},{"given":"Yoshio","family":"Okamoto","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0087-853X","authenticated-orcid":false,"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[]},{"given":"Yushi","family":"Uno","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"key":"921_CR1","doi-asserted-by":"publisher","DOI":"10.23638\/DMTCS-20-1-15","author":"MD Barrus","year":"2018","unstructured":"Barrus, M.D.: Weakly threshold graphs. Discrete Math. Theor. Comput. Sci. (2018). https:\/\/doi.org\/10.23638\/DMTCS-20-1-15","journal-title":"Discrete Math. Theor. Comput. Sci."},{"issue":"8","key":"921_CR2","doi-asserted-by":"publisher","first-page":"2159","DOI":"10.1016\/j.disc.2018.04.023","volume":"341","author":"R Behr","year":"2018","unstructured":"Behr, R., Sivaraman, V., Zaslavsky, T.: Mock threshold graphs. Discret. Math. 341(8), 2159\u20132178 (2018). https:\/\/doi.org\/10.1016\/j.disc.2018.04.023","journal-title":"Discret. Math."},{"issue":"2","key":"921_CR3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1002\/jgt.3190090207","volume":"9","author":"C Benzaken","year":"1985","unstructured":"Benzaken, C., Hammer, P.L., de Werra, D.: Threshold characterization of graphs with Dilworth number two. J. Graph Theory 9(2), 245\u2013267 (1985). https:\/\/doi.org\/10.1002\/jgt.3190090207","journal-title":"J. Graph Theory"},{"issue":"3","key":"921_CR4","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/140978053","volume":"58","author":"T Calamoneri","year":"2016","unstructured":"Calamoneri, T., Sinaimeri, B.: Pairwise compatibility graphs: a survey. SIAM Rev. 58(3), 445\u2013460 (2016). https:\/\/doi.org\/10.1137\/140978053","journal-title":"SIAM Rev."},{"issue":"1\u20132","key":"921_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/bf02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai, T.: Transitiv orientierbare graphen. Acta Mathematica Academiae Scientiarum Hungaricae 18(1\u20132), 25\u201366 (1967). https:\/\/doi.org\/10.1007\/bf02020961","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"921_CR6","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. North Holland, Amsterdam (2004)","edition":"2"},{"key":"921_CR7","doi-asserted-by":"publisher","unstructured":"Hamburger, P., McConnell, R.M., P\u00f3r, A., Spinrad, J.P., Xu, Z.: Double threshold digraphs. In: MFCS 2018, volume 117 of LIPIcs, pp. 69:1\u201369:12 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2018.69","DOI":"10.4230\/LIPIcs.MFCS.2018.69"},{"issue":"3","key":"921_CR8","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1137\/0606049","volume":"6","author":"PL Hammer","year":"1985","unstructured":"Hammer, P.L., Mahadev, N.V.R.: Bithreshold graphs. SIAM J. Algebr. Discrete Methods 6(3), 497\u2013506 (1985). https:\/\/doi.org\/10.1137\/0606049","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"921_CR9","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1016\/j.tcs.2014.10.002","volume":"562","author":"P Heggernes","year":"2015","unstructured":"Heggernes, P., van\u2019t Hof, P., Meister, D., Villanger, Y.: Induced subgraph isomorphism on proper interval and bipartite permutation graphs. Theor. Comput. Sci. 562, 252\u2013269 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2014.10.002","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"921_CR10","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/jgt.20006","volume":"46","author":"P Hell","year":"2004","unstructured":"Hell, P., Huang, J.: Interval bigraphs and circular arc graphs. J. Graph Theory 46(4), 313\u2013327 (2004). https:\/\/doi.org\/10.1002\/jgt.20006","journal-title":"J. Graph Theory"},{"key":"921_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-021-01029-7","author":"RE Jamison","year":"2021","unstructured":"Jamison, R.E., Sprague, A.P.: Double-threshold permutation graphs. J. Algebr. Combin. (2021). https:\/\/doi.org\/10.1007\/s10801-021-01029-7","journal-title":"J. Algebr. Combin."},{"issue":"4","key":"921_CR12","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1002\/jgt.22541","volume":"94","author":"RE Jamison","year":"2020","unstructured":"Jamison, R.E., Sprague, A.P.: Multithreshold graphs. J. Graph Theory 94(4), 518\u2013530 (2020). https:\/\/doi.org\/10.1002\/jgt.22541","journal-title":"J. Graph Theory"},{"key":"921_CR13","doi-asserted-by":"publisher","unstructured":"Kearney, P.E., Munro, J.I., Phillips, D.: Efficient generation of uniform samples from phylogenetic trees. In: WABI 2003, volume 2812 of Lecture Notes in Computer Science, pp. 177\u2013189. Springer (2003). https:\/\/doi.org\/10.1007\/978-3-540-39763-2_14","DOI":"10.1007\/978-3-540-39763-2_14"},{"key":"921_CR14","unstructured":"Ma, T.-H.: On the threshold dimension 2 graphs. Technical report, Institute of Information Science, Nankang, Taipei, Taiwan (1993)"},{"key":"921_CR15","volume-title":"Threshold Graphs and Related Topics","author":"NVR Mahadev","year":"1995","unstructured":"Mahadev, N.V.R., Peled, U.N.: Threshold Graphs and Related Topics. North Holland, Amsterdam (1995)"},{"issue":"1\u20133","key":"921_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discret. Math. 201(1\u20133), 189\u2013241 (1999). https:\/\/doi.org\/10.1016\/S0012-365X(98)00319-7","journal-title":"Discret. Math."},{"issue":"3","key":"921_CR17","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/jgt.3190120307","volume":"12","author":"CL Monma","year":"1988","unstructured":"Monma, C.L., Reed, B.A., Trotter, W.T.: Threshold tolerance graphs. J. Graph Theory 12(3), 343\u2013362 (1988). https:\/\/doi.org\/10.1002\/jgt.3190120307","journal-title":"J. Graph Theory"},{"issue":"3","key":"921_CR18","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1007\/s00373-020-02168-7","volume":"36","author":"GJ Puleo","year":"2020","unstructured":"Puleo, G.J.: Some results on multithreshold graphs. Graphs Combin. 36(3), 913\u2013919 (2020). https:\/\/doi.org\/10.1007\/s00373-020-02168-7","journal-title":"Graphs Combin."},{"key":"921_CR19","doi-asserted-by":"publisher","unstructured":"Raschle, T., Simon, K.: Recognition of graphs with threshold dimension two. In STOC, pp. 650\u2013661. ACM (1995). https:\/\/doi.org\/10.1145\/225058.225283","DOI":"10.1145\/225058.225283"},{"key":"921_CR20","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."},{"issue":"2","key":"921_CR21","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1137\/S0895480190177145","volume":"7","author":"MK Sen","year":"1994","unstructured":"Sen, M.K., Sanyal, B.K.: Indifference digraphs: a generalization of indifference graphs and semiorders. SIAM J. Discrete Math. 7(2), 157\u2013165 (1994). https:\/\/doi.org\/10.1137\/S0895480190177145","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"921_CR22","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"JP Spinrad","year":"1987","unstructured":"Spinrad, J.P., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discrete Appl. Math. 18(3), 279\u2013292 (1987). https:\/\/doi.org\/10.1016\/S0166-218X(87)80003-3","journal-title":"Discrete Appl. Math."},{"key":"921_CR23","first-page":"151","volume":"112","author":"AP Sprague","year":"1995","unstructured":"Sprague, A.P.: Recognition of bipartite permutation graphs. Congr. Numer. 112, 151\u2013161 (1995)","journal-title":"Congr. Numer."},{"issue":"5","key":"921_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0020-0190(98)00112-4","volume":"67","author":"A Sterbini","year":"1998","unstructured":"Sterbini, A., Raschle, T.: An $$O(n^3)$$ time algorithm for recognizing threshold dimension 2 graphs. Inf. Process. Lett. 67(5), 255\u2013259 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00112-4","journal-title":"Inf. Process. Lett."},{"issue":"1\u20133","key":"921_CR25","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0012-365X(97)81840-7","volume":"178","author":"DB West","year":"1998","unstructured":"West, D.B.: Short proofs for interval digraphs. Discrete Math. 178(1\u20133), 287\u2013292 (1998). https:\/\/doi.org\/10.1016\/S0012-365X(97)81840-7","journal-title":"Discrete Math."},{"issue":"10","key":"921_CR26","doi-asserted-by":"publisher","first-page":"3066","DOI":"10.1007\/s00453-020-00712-8","volume":"82","author":"M Xiao","year":"2020","unstructured":"Xiao, M., Nagamochi, H.: Characterizing star-PCGs. Algorithmica 82(10), 3066\u20133090 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00712-8","journal-title":"Algorithmica"},{"issue":"3","key":"921_CR27","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"J-H Yan","year":"1996","unstructured":"Yan, J.-H., Chen, J.-J., Gerard, J.C.: Quasi-threshold graphs. Discrete Appl. Math. 69(3), 247\u2013255 (1996). https:\/\/doi.org\/10.1016\/0166-218X(96)00094-7","journal-title":"Discrete Appl. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00921-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00921-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00921-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:09:09Z","timestamp":1647443349000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00921-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["921"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00921-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,1,6]]},"assertion":[{"value":"11 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}