{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T02:51:06Z","timestamp":1725677466327},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642296994"},{"type":"electronic","value":"9783642297007"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29700-7_31","type":"book-chapter","created":{"date-parts":[[2012,4,28]],"date-time":"2012-04-28T12:25:56Z","timestamp":1335615956000},"page":"339-350","source":"Crossref","is-referenced-by-count":0,"title":["The Black-and-White Coloring Problem on Distance-Hereditary Graphs and Strongly Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Ton","family":"Kloks","sequence":"first","affiliation":[]},{"given":"Sheung-Hung","family":"Poon","sequence":"additional","affiliation":[]},{"given":"Feng-Ren","family":"Tsai","sequence":"additional","affiliation":[]},{"given":"Yue-Li","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1016\/0095-8956(82)90056-9","volume":"33","author":"B. Acharya","year":"1982","unstructured":"Acharya, B., Las Vergnas, M.: Hypergraphs with cyclomatic number zero, triangulated graphs, and an inequality. Journal of Combinatorial Theory, Series B\u00a033, 52\u201356 (1982)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"31_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02579287","volume":"3","author":"R. Anstee","year":"1983","unstructured":"Anstee, R.: Hypergraphs with no special cycles. Combinatorica\u00a03, 141\u2013146 (1983)","journal-title":"Combinatorica"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0196-6774(84)90028-2","volume":"5","author":"R. Anstee","year":"1984","unstructured":"Anstee, R., Farber, M.: Characterizations of totally balanced matrices. Journal of Algorithms\u00a05, 215\u2013230 (1984)","journal-title":"Journal of Algorithms"},{"key":"31_CR4","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"H. Bandelt","year":"1986","unstructured":"Bandelt, H., Mulder, H.: Distance-hereditary graphs. Journal of Combinatorial Theory, Series B\u00a041, 182\u2013208 (1986)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/S0021-9800(69)80120-1","volume":"6","author":"L. Beineke","year":"1969","unstructured":"Beineke, L., Pippert, R.: The number of labeled k-dimensional trees. Journal of Combinatorial Theory\u00a06, 200\u2013205 (1969)","journal-title":"Journal of Combinatorial Theory"},{"key":"31_CR6","doi-asserted-by":"crossref","first-page":"133","DOI":"10.7155\/jgaa.00180","volume":"13","author":"D. Berend","year":"2009","unstructured":"Berend, D., Zucker, S.: The black-and-white coloring problem on trees. Journal of Graph Algorithms and Applications\u00a013, 133\u2013152 (2009)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Booth, K., Lueker, G.: Linear algorithms to recognize interval graphs and test for the consecutive ones property. In: Proceedings STOC 1975, pp. 255\u2013265. ACM (1975)","DOI":"10.1145\/800116.803776"},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1137\/S0895480197326346","volume":"12","author":"H. Broersma","year":"1999","unstructured":"Broersma, H., Kloks, T., Kratsch, D., M\u00fcller, H.: Independent sets in asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics\u00a012, 276\u2013287 (1999)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"31_CR9","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0012-365X(83)90088-2","volume":"47","author":"A. Brouwer","year":"1983","unstructured":"Brouwer, A., Duchet, P., Schrijver, A.: Graphs whose neighborhoods have no special cycle. Discrete Mathematics\u00a047, 177\u2013182 (1983)","journal-title":"Discrete Mathematics"},{"key":"31_CR10","unstructured":"Brouwer, A., Kolen, A.: A super-balanced hypergraph has a nest point. Technical Report ZW\u00a0146, Mathematisch Centrum, Amsterdam (1980)"},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/3-540-63890-3_37","volume-title":"Algorithms and Computation","author":"M. Chang","year":"1997","unstructured":"Chang, M., Hsieh, S., Chen, G.: Dynamic Programming on Distance-Hereditary Graphs. In: Leong, H.-V., Jain, S., Imai, H. (eds.) ISAAC 1997. LNCS, vol.\u00a01350, pp. 344\u2013353. Springer, Heidelberg (1997)"},{"key":"31_CR12","unstructured":"Chv\u00e1tal, V., Hammer, P.: Aggregation of inequalities in integer programming. Technical Report STAN-CS-75-518, Stanford University, California (1975)"},{"key":"31_CR13","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"D. Corneil","year":"1981","unstructured":"Corneil, D., Lerchs, H., Stewart-Burlingham, L.: Complement reducible graphs. Discrete Applied Mathematics\u00a03, 163\u2013174 (1981)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR14","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D. Corneil","year":"1985","unstructured":"Corneil, D., Perl, Y., Stewart, L.: A linear recognition algorithm for cographs. SIAM Journal on Computing\u00a014, 926\u2013934 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G. Dirac","year":"1961","unstructured":"Dirac, G.: On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg\u00a025, 71\u201376 (1961)","journal-title":"Abhandlungen aus dem Mathematischen Seminar der Universit\u00e4t Hamburg"},{"key":"31_CR16","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(83)90154-1","volume":"43","author":"M. Farber","year":"1983","unstructured":"Farber, M.: Characterizations of strongly chordal graphs. Discrete Mathematics\u00a043, 173\u2013189 (1983)","journal-title":"Discrete Mathematics"},{"key":"31_CR17","first-page":"311","volume":"19","author":"S. F\u00f6ldes","year":"1977","unstructured":"F\u00f6ldes, S., Hammer, P.: Split graphs. Congressus Numerantium\u00a019, 311\u2013315 (1977)","journal-title":"Congressus Numerantium"},{"key":"31_CR18","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. Journal of Combinatorial Theory, Series B\u00a016, 47\u201356 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"31_CR19","doi-asserted-by":"publisher","first-page":"539","DOI":"10.4153\/CJM-1964-055-5","volume":"16","author":"P. Gilmore","year":"1964","unstructured":"Gilmore, P., Hoffman, A.: A characterization of comparability graphs and of interval graphs. The Canadian Journal of Mathematics\u00a016, 539\u2013548 (1964)","journal-title":"The Canadian Journal of Mathematics"},{"key":"31_CR20","first-page":"113","volume":"1","author":"A. Hajnal","year":"1958","unstructured":"Hajnal, A., Sur\u00e1nyi, J.: \u00dcber die Aufl\u00f6sung von Graphen in vollst\u00e4ndige Teilgraphen. Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae \u2013 Sectio Mathematicae\u00a01, 113\u2013121 (1958)","journal-title":"Annales Universitatis Scientiarum Budapestinensis de Rolando E\u00f6tv\u00f6s Nominatae \u2013 Sectio Mathematicae"},{"key":"31_CR21","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0166-218X(90)90092-Q","volume":"28","author":"P. Hammer","year":"1990","unstructured":"Hammer, P., Peled, U., Sun, X.: Difference graphs. Discrete Applied Mathematics\u00a028, 35\u201344 (1990)","journal-title":"Discrete Applied Mathematics"},{"key":"31_CR22","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1016\/S0012-365X(96)00187-2","volume":"165","author":"P. Hansen","year":"1997","unstructured":"Hansen, P., Hertz, A., Quinodos, N.: Splitting trees. Discrete Mathematics\u00a0165, 403\u2013419 (1997)","journal-title":"Discrete Mathematics"},{"key":"31_CR23","unstructured":"Hoffman, A., Kolen, A., Sakarovitch, M.: Totally-balanced and greedy matrices. Technical Report BW\u00a0165\/82, Mathematisch Centrum, Amsterdam (1982)"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"28","author":"E. Howorka","year":"1977","unstructured":"Howorka, E.: A characterization of distance-hereditary graphs. The Quarterly Journal of Mathematics\u00a028, 417\u2013420 (1977)","journal-title":"The Quarterly Journal of Mathematics"},{"key":"31_CR25","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1016\/0196-6774(87)90021-6","volume":"8","author":"D. Johnson","year":"1987","unstructured":"Johnson, D.: The NP-completeness column: An ongoing guide. Journal of Algorithms\u00a08, 438\u2013448 (1987)","journal-title":"Journal of Algorithms"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"Kloks, T.: Treewidth \u2013 Computations and Approximations. LNCS, vol.\u00a0842. Springer, Heidelberg (1994)","DOI":"10.1007\/BFb0045375"},{"key":"31_CR27","unstructured":"Kloks, T., Poon, S., Tsai, F., Wang, Y.: The black-and-white coloring problem on distance-hereditary graphs and strongly chordal graphs. Manuscript on ArXiv: 1111.0867v1 (2011)"},{"key":"31_CR28","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0012-365X(85)90156-6","volume":"57","author":"J. Lehel","year":"1985","unstructured":"Lehel, J.: A characterization of totally balanced hypergraphs. Discrete Mathematics\u00a057, 59\u201365 (1985)","journal-title":"Discrete Mathematics"},{"key":"31_CR29","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. Lekkerkerker","year":"1962","unstructured":"Lekkerkerker, C., Boland, D.: Representation of finite graphs by a set of intervals on the real line. Fundamenta Mathematicae\u00a051, 45\u201364 (1962)","journal-title":"Fundamenta Mathematicae"},{"key":"31_CR30","unstructured":"Mahadev, N., Peled, U.: Threshold graphs and related topics. Elsevier Series Annals of Discrete Mathematics 56 (1995)"},{"key":"31_CR31","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/S0021-9800(69)80119-5","volume":"6","author":"J. Moon","year":"1969","unstructured":"Moon, J.: The number of labeled k-trees. Journal of Combinatorial Theory\u00a06, 196\u2013199 (1969)","journal-title":"Journal of Combinatorial Theory"},{"key":"31_CR32","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D. Rose","year":"1970","unstructured":"Rose, D.: Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications\u00a032, 597\u2013609 (1970)","journal-title":"Journal of Mathematical Analysis and Applications"},{"key":"31_CR33","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0012-365X(74)90042-9","volume":"7","author":"D. Rose","year":"1974","unstructured":"Rose, D.: On simple characterizations of k-trees. Discrete Mathematics\u00a07, 317\u2013322 (1974)","journal-title":"Discrete Mathematics"},{"key":"31_CR34","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the partial order dimension problem. SIAM Journal on Algebraic and Discrete Methods\u00a03, 351\u2013358 (1982)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29700-7_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:14:06Z","timestamp":1620126846000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29700-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642296994","9783642297007"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29700-7_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}