{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:47Z","timestamp":1759638947380},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540725039"},{"type":"electronic","value":"9783540725046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72504-6_22","type":"book-chapter","created":{"date-parts":[[2007,7,22]],"date-time":"2007-07-22T11:36:39Z","timestamp":1185104199000},"page":"244-255","source":"Crossref","is-referenced-by-count":4,"title":["On the Treewidth and Pathwidth of Biconvex Bipartite Graphs"],"prefix":"10.1007","author":[{"given":"Sheng-Lung","family":"Peng","sequence":"first","affiliation":[]},{"given":"Yi-Chuan","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(99)00217-6","volume":"103","author":"N. Abbas","year":"2000","unstructured":"Abbas, N., Stewart, L.K.: Biconvex graphs: ordering and algorithms. Discrete Applied Mathematics\u00a0103, 1\u201319 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"22_CR3","first-page":"1","volume":"11","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica\u00a011, 1\u201323 (1993)","journal-title":"Acta Cybernetica"},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. Journal of Algorithms\u00a021, 358\u2013402 (1996)","journal-title":"Journal of Algorithms"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"Bodlaender, H.L., Kloks, T., Kratsch, D.: Treewidth and pathwidht of permutation graphs. SIAM Journal on Discrete Mathematics\u00a08, 606\u2013616 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00008","volume":"2","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L., et al.: Treewidth and minimum fill-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications\u00a02, 1\u201323 (1998)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"Bodlaender, H.L., M\u00f6hring, R.H.: The pathwidth and treewidth of cographs. SIAM Journal on Discrete Mathematics\u00a06, 181\u2013188 (1993)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR8","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Treewidth and small separators for graphs with small chordality. Technical Report UU-CS-1995-02, Department of Computer Science, Utrecht University, Utrecht (1995)"},{"key":"22_CR9","unstructured":"Broersma, H., Dahlhaus, E., Kloks, T.: A linear time algorithm for minimum fill in and treewidth for distance hereditary graphs. In: Scientific program 5th Twente Workshop on Graphs and Combinatorial Optimization, pp. 48\u201350 (1997)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"1993","unstructured":"Gustedt, J.: On the pathwidth of chordal graphs. Discrete Applied Mathematics\u00a045, 233\u2013248 (1993)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF01462229","volume":"11","author":"M. Habib","year":"1994","unstructured":"Habib, M., M\u00f6hring, R.H.: Treewidth of cocomparability graphs and a new order-theoretical parameter. Order\u00a011, 47\u201360 (1994)","journal-title":"Order"},{"key":"22_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-57568-5_240","volume-title":"Algorithms and Computation","author":"T. Kloks","year":"1993","unstructured":"Kloks, T.: Treewidth of circle graphs. In: Ng, K.W., et al. (eds.) ISAAC 1993. LNCS, vol.\u00a0762, pp. 108\u2013117. Springer, Heidelberg (1993)"},{"key":"22_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","first-page":"508","volume-title":"Algorithms - ESA \u201993","author":"T. Kloks","year":"1993","unstructured":"Kloks, T., et al.: Computing treewidth and minimum fill-in: all you need are the minimal separators. In: Lengauer, T. (ed.) ESA 1993. LNCS, vol.\u00a0726, pp. 508\u2013508. Springer, Heidelberg (1993), Erratum: ESA 1994, LNCS 855, pp. 508\u2013508 (1994)"},{"key":"22_CR15","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"T. Kloks","year":"1995","unstructured":"Kloks, T., Kratsch, D.: Treewidth of chordal bipartite graphs. Journal of Algorithms\u00a019, 266\u2013281 (1995)","journal-title":"Journal of Algorithms"},{"key":"22_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-59071-4_41","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Kloks","year":"1995","unstructured":"Kloks, T., Kratsch, K., M\u00fcller, H.: Dominoes. In: Mayr, E.W., Schmidt, G., Tinhofer, G. (eds.) WG 1994. LNCS, vol.\u00a0903, pp. 106\u2013120. Springer, Heidelberg (1995)"},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/BF00264533","volume":"15","author":"W. Lipski","year":"1981","unstructured":"Lipski, W., Preparata Jr., F.P.: Efficient Algorithms for finding maximum matchings in convex bipartite graphs and related problems. Acta Informatica\u00a015, 329\u2013346 (1981)","journal-title":"Acta Informatica"},{"key":"22_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/11604686_9","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"D. Meister","year":"2005","unstructured":"Meister, D.: Computing treewidth and minimum fill-in for permutation graphs in linear time. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 91\u2013102. Springer, Heidelberg (2005)"},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B., Sudborough, I.H.: Min cut in NP-complete for edge weighted trees. Theoretical Computer Science\u00a058, 209\u2013229 (1988)","journal-title":"Theoretical Computer Science"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., Brandstadt, A., Stewart, L.: Bipartite permutation graphs. Discrete Applied Mathematics\u00a018, 279\u2013292 (1987)","journal-title":"Discrete Applied Mathematics"},{"key":"22_CR21","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S0895480191193789","volume":"7","author":"R. Sundaram","year":"1994","unstructured":"Sundaram, R., Singh, K.S., Rangan, C.P.: Treewidth of circular arc graphs. SIAM Journal on Discrete Mathematics\u00a07, 647\u2013655 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"22_CR22","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M.: Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Discrete Methods\u00a02, 77\u201379 (1981)","journal-title":"SIAM Journal on Algebraic Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72504-6_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T09:38:07Z","timestamp":1619516287000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72504-6_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540725039","9783540725046"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72504-6_22","relation":{},"subject":[]}}