{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:46:11Z","timestamp":1770972371312,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T00:00:00Z","timestamp":1322870400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,5]]},"DOI":"10.1007\/s00224-011-9378-8","type":"journal-article","created":{"date-parts":[[2011,12,3]],"date-time":"2011-12-03T08:34:28Z","timestamp":1322901268000},"page":"721-738","source":"Crossref","is-referenced-by-count":12,"title":["Linear-Time Algorithm for the Paired-Domination Problem in Convex Bipartite Graphs"],"prefix":"10.1007","volume":"50","author":[{"given":"Ruo-Wei","family":"Hung","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,12,3]]},"reference":[{"key":"9378_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":"Arikati, S.R., Pandu Rangan, C.: Linear algorithm for optimal path cover problem on interval graphs. Inf. Process. Lett. 35, 149\u2013153 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9378_CR2","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/j.tcs.2007.05.012","volume":"381","author":"K. Asdre","year":"2007","unstructured":"Asdre, K., Nikolopoulos, S.D.: NP-completeness results for some problems on subclasses of bipartite and chordal graphs. Theor. Comput. Sci. 381, 248\u2013259 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9378_CR3","unstructured":"Bang-Jensen, J., Huang, J., MacGillivray, G., Yeo, A.: Domination in convex bipartite and convex-round graphs. Tech. Rep. PP-1999-08, University of Southern Denmark (1999)"},{"key":"9378_CR4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"Booth, K., Lueker, G.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13, 335\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"9378_CR5","first-page":"125","volume-title":"13th International Parallel Processing Symposium (IPPS\u201999)","author":"P. Bose","year":"1999","unstructured":"Bose, P., Chan, A., Dehne, F., Latzel, M.: Coarse grained parallel maximum matching in convex bipartite graphs. In: 13th International Parallel Processing Symposium (IPPS\u201999), pp. 125\u2013129 (1999)"},{"key":"9378_CR6","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1007\/978-3-540-74456-6_37","volume":"4708","author":"G.S. Brodal","year":"2007","unstructured":"Brodal, G.S., Georgiadis, L., Hansen, K.A., Katriel, I.: Dynamic matchings in convex bipartite graphs. Lect. Notes Comput. Sci. 4708, 406\u2013417 (2007)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9378_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"9378_CR8","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.tcs.2007.04.006","volume":"381","author":"A. Brandst\u00e4dt","year":"2007","unstructured":"Brandst\u00e4dt, A., Eschen, E.M., Sritharan, R.: The induced matching and chain subgraph cover problems for convex bipartite graphs. Theor. Comput. Sci. 381, 260\u2013265 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"9378_CR9","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.parco.2007.11.004","volume":"34","author":"A. Chan","year":"2008","unstructured":"Chan, A., Dehne, F., Bose, P., Latzel, M.: Coarse grained parallel algorithms for graph matching. Parallel Comput. 34, 47\u201362 (2008)","journal-title":"Parallel Comput."},{"key":"9378_CR10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1097-0037(199908)34:1<1::AID-NET1>3.0.CO;2-C","volume":"34","author":"M.S. Chang","year":"1999","unstructured":"Chang, M.S., Peng, S.L., Liaw, J.L.: Deferred-query: an efficient approach for some problems on interval graphs. Networks 34, 1\u201310 (1999)","journal-title":"Networks"},{"key":"9378_CR11","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/j.ipl.2009.09.014","volume":"110","author":"L. Chen","year":"2009","unstructured":"Chen, L., Lu, C., Zeng, Z.: A linear-time algorithm for paired-domination problem in strongly chordal graphs. Inf. Process. Lett. 110, 20\u201323 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9378_CR12","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/s10878-008-9177-6","volume":"19","author":"L. Chen","year":"2010","unstructured":"Chen, L., Lu, C., Zeng, Z.: Labelling algorithms for paired-domination problems in block and interval graphs. J. Comb. Optim. 19, 457\u2013470 (2010)","journal-title":"J. Comb. Optim."},{"key":"9378_CR13","doi-asserted-by":"crossref","first-page":"2077","DOI":"10.1016\/j.dam.2007.05.011","volume":"155","author":"T.C.E. Cheng","year":"2007","unstructured":"Cheng, T.C.E., Kang, L., Ng, C.T.: Paired domination on interval and circular-arc graphs. Discrete Appl. Math. 155, 2077\u20132086 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9378_CR14","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1016\/j.dam.2008.02.015","volume":"157","author":"T.C.E. Cheng","year":"2009","unstructured":"Cheng, T.C.E., Kang, L., Shan, E.: A polynomial-time algorithm for the paired-domination problem on permutation graphs. Discrete Appl. Math. 157, 262\u2013271 (2009)","journal-title":"Discrete Appl. Math."},{"key":"9378_CR15","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"9378_CR16","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0020-0190(90)90147-P","volume":"36","author":"P. Damaschke","year":"1990","unstructured":"Damaschke, P., M\u00fcller, H., Kratsch, D.: Domination in convex and chordal bipartite graphs. Inf. Process. Lett. 36, 231\u2013236 (1990)","journal-title":"Inf. Process. Lett."},{"key":"9378_CR17","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0743-7315(84)90004-2","volume":"1","author":"E. Dekel","year":"1984","unstructured":"Dekel, E., Sahni, S.: A parallel matching for convex bipartite graphs and applications to scheduling. J. Parallel Distrib. Comput. 1, 185\u2013205 (1984)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9378_CR18","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0167-6377(84)90068-3","volume":"3","author":"G. Gallo","year":"1984","unstructured":"Gallo, G.: An O(nlogn) algorithm for the convex bipartite matching problem. Oper. Res. Lett. 3, 31\u201334 (1984)","journal-title":"Oper. Res. Lett."},{"key":"9378_CR19","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1002\/nav.3800140304","volume":"14","author":"F. Glover","year":"1967","unstructured":"Glover, F.: Maximum matching in a convex bipartite graph. Nav. Res. Logist. Q. 14, 313\u2013316 (1967)","journal-title":"Nav. Res. Logist. Q."},{"key":"9378_CR20","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F","volume":"32","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Slater, P.J.: Paired-domination in graphs. Networks 32, 199\u2013206 (1998)","journal-title":"Networks"},{"key":"9378_CR21","volume-title":"Fundamentals of Domination in Graphs","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Dekker, New\u00a0York (1998)"},{"key":"9378_CR22","volume-title":"Domination in Graphs: Advanced Topics","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in Graphs: Advanced Topics. Dekker, New\u00a0York (1998)"},{"key":"9378_CR23","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1016\/j.aml.2010.11.030","volume":"24","author":"R.W. Hung","year":"2011","unstructured":"Hung, R.W., Chang, M.S.: Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs. Appl. Math. Lett. 24, 648\u2013652 (2011)","journal-title":"Appl. Math. Lett."},{"key":"9378_CR24","first-page":"365","volume-title":"Proceedings of the International MultiConference of Engineers and Computer Scientists 2010 (IMECS\u20192010)","author":"R.W. Hung","year":"2010","unstructured":"Hung, R.W., Laio, C.H., Wang, C.K.: Efficient algorithm for the paired-domination problem in convex bipartite graphs. In: Proceedings of the International MultiConference of Engineers and Computer Scientists 2010 (IMECS\u20192010), vol. I, pp. 365\u2013369 (2010)"},{"key":"9378_CR25","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1287\/ijoc.1070.0232","volume":"20","author":"I. Katriel","year":"2008","unstructured":"Katriel, I.: Matchings in node-weighted convex bipartite graphs. INFORMS J. Comput. 20, 205\u2013211 (2008)","journal-title":"INFORMS J. Comput."},{"key":"9378_CR26","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/j.endm.2009.02.018","volume":"32","author":"N. Korpelainen","year":"2009","unstructured":"Korpelainen, N.: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs. Electron. Notes Discrete Math. 32, 133\u2013140 (2009)","journal-title":"Electron. Notes Discrete Math."},{"key":"9378_CR27","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/978-3-642-10217-2_36","volume":"5874","author":"E. Lappas","year":"2009","unstructured":"Lappas, E., Nikolopoulos, S.D., Palios, L.: An O(n)-time algorithm for the paired-domination problem on permutation graphs. Lect. Notes Comput. Sci. 5874, 368\u2013379 (2009)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9378_CR28","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s002360050088","volume":"34","author":"Y.D. Liang","year":"1997","unstructured":"Liang, Y.D., Chang, M.S.: Minimum feedback vertex sets in cocomparability graphs and convex bipartite graphs. Acta Inform. 34, 337\u2013346 (1997)","journal-title":"Acta Inform."},{"key":"9378_CR29","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W. Lipski","year":"1981","unstructured":"Lipski, W., Preparata, F.: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Inform. 15, 329\u2013346 (1981)","journal-title":"Acta Inform."},{"key":"9378_CR30","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0012-365X(95)00057-4","volume":"156","author":"H. M\u00fcller","year":"1996","unstructured":"M\u00fcller, H.: Hamiltonian circuits in chordal bipartite graphs. Discrete Math. 156, 291\u2013298 (1996)","journal-title":"Discrete Math."},{"key":"9378_CR31","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-642-14031-0_17","volume":"6196","author":"D. Nussbaum","year":"2010","unstructured":"Nussbaum, D., Pu, S., Sack, J.R., Uno, T., Zarrabi-Zadeh, H.: Finding maximum edge bicliques in convex bipartite graphs. Lect. Notes Comput. Sci. 6196, 140\u2013149 (2010)","journal-title":"Lect. Notes Comput. Sci."},{"key":"9378_CR32","first-page":"81","volume":"84","author":"E. Park","year":"2008","unstructured":"Park, E., Park, K.: An improved Boolean circuit for maximum matching in a convex bipartite graph. Fundam. Inform. 84, 81\u2013107 (2008)","journal-title":"Fundam. Inform."},{"key":"9378_CR33","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1023\/A:1021338214295","volume":"25","author":"H. Qiao","year":"2003","unstructured":"Qiao, H., Kang, L., Cardei, M., Du, D.Z.: Paired-domination of trees. J. Glob. Optim. 25, 43\u201354 (2003)","journal-title":"J. Glob. Optim."},{"key":"9378_CR34","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00453-007-9006-9","volume":"53","author":"J. Soares","year":"2009","unstructured":"Soares, J., Stefanes, M.A.: Algorithms for maximum independent set in convex bipartite graphs. Algorithmica 53, 35\u201349 (2009)","journal-title":"Algorithmica"},{"key":"9378_CR35","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0020-0190(95)94093-8","volume":"56","author":"A. Srinivasan","year":"1995","unstructured":"Srinivasan, A., Madhukar, K., Nagavamsi, P., Pandu Rangan, C., Chang, M.S.: Edge domination on bipartite permutation graphs and cotriangulated graphs. Inf. Process. Lett. 56, 165\u2013171 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"9378_CR36","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0898-1221(96)00079-X","volume":"31","author":"G. Steiner","year":"1996","unstructured":"Steiner, G., Yeoman, J.: A linear time algorithm for maximum matchings in convex, bipartite graphs. Comput. Math. Appl. 31(12), 91\u201396 (1996)","journal-title":"Comput. Math. Appl."},{"key":"9378_CR37","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.ins.2004.11.008","volume":"171","author":"S.J. Yang","year":"2005","unstructured":"Yang, S.J.: Efficient algorithms to solve the link-orientation problem for multi-square, convex-bipartite, and convex-split networks. Inf. Sci. 171, 475\u2013493 (2005)","journal-title":"Inf. Sci."},{"key":"9378_CR38","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0020-0255(03)00182-8","volume":"157","author":"W.C.K. Yen","year":"2003","unstructured":"Yen, W.C.K.: The bottleneck independent domination on the classes of bipartite graphs and block graphs. Inf. Sci. 157, 199\u2013215 (2003)","journal-title":"Inf. Sci."},{"key":"9378_CR39","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/S0304-3975(97)00036-4","volume":"205","author":"C.W. Yu","year":"1998","unstructured":"Yu, C.W., Chen, G.H., Ma, T.H.: On the complexity of the k-chain subgraph cover problem. Theor. Comput. Sci. 205, 85\u201398 (1998)","journal-title":"Theor. Comput. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9378-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9378-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9378-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:54:23Z","timestamp":1558698863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9378-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12,3]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,5]]}},"alternative-id":["9378"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9378-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12,3]]}}}