{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:49:50Z","timestamp":1743011390491},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642258695"},{"type":"electronic","value":"9783642258701"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-25870-1_6","type":"book-chapter","created":{"date-parts":[[2011,11,30]],"date-time":"2011-11-30T08:32:45Z","timestamp":1322641965000},"page":"47-58","source":"Crossref","is-referenced-by-count":7,"title":["Graph Classes with Structured Neighborhoods and Algorithmic Applications"],"prefix":"10.1007","author":[{"given":"R\u00e9my","family":"Belmonte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Vatshelle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"6_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-16926-7_16","volume-title":"Graph Theoretic Concepts in Computer Science","author":"I. Adler","year":"2010","unstructured":"Adler, I., Bui-Xuan, B.-M., Rabinovich, Y., Renault, G., Telle, J.A., Vatshelle, M.: On the Boolean-Width of a Graph: Structure and Applications. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol.\u00a06410, pp. 159\u2013170. Springer, Heidelberg (2010)"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/BFb0028791","volume-title":"Fundamentals of Computation Theory","author":"A. Brandst\u00e4dt","year":"1985","unstructured":"Brandst\u00e4dt, A., Kratsch, D.: On the Restriction of Some np-Complete Graph Problems to Permutation Graphs. In: Budach, L. (ed.) FCT 1985. LNCS, vol.\u00a0199, pp. 53\u201362. Springer, Heidelberg (1985)"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"6_CR4","unstructured":"Brandst\u00e4dt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Comb. 67 (2003)"},{"key":"6_CR5","unstructured":"Bui-Xuan, B.M., Telle, J.A., Vatshelle, M.: Fast algorithms for vertex subset and vertex partitioning problems on graphs of low boolean-width. arXiv"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-11269-0_5","volume-title":"Parameterized and Exact Computation","author":"B.-M. Bui-Xuan","year":"2009","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-Width of Graphs. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 61\u201374. Springer, Heidelberg (2009)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/BFb0015415","volume-title":"Algorithms and Computations","author":"M.S. Chang","year":"1995","unstructured":"Chang, M.S.: Weighted Domination on Cocomparability Graphs. In: Staples, J., Katoh, N., Eades, P., Moffat, A. (eds.) ISAAC 1995. LNCS, vol.\u00a01004, pp. 122\u2013131. Springer, Heidelberg (1995)"},{"issue":"6","key":"6_CR8","doi-asserted-by":"publisher","first-page":"1671","DOI":"10.1137\/S0097539792238431","volume":"27","author":"M.S. Chang","year":"1998","unstructured":"Chang, M.S.: Efficient algorithms for the domination problems on interval and circular-arc graphs. SIAM J. on Computing\u00a027(6), 1671\u20131694 (1998)","journal-title":"SIAM J. on Computing"},{"key":"6_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0166-218X(84)90088-X","volume":"9","author":"D.G. Corneil","year":"1984","unstructured":"Corneil, D.G., Perl, Y.: Clustering and domination in perfect graphs. Discrete Applied Math.\u00a09, 27\u201340 (1984)","journal-title":"Discrete Applied Math."},{"issue":"2","key":"6_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst.\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"5","key":"6_CR11","doi-asserted-by":"publisher","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.\u00a036(5), 231\u2013236 (1990)","journal-title":"Inf. Process. Lett."},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1007\/3-540-36087-5_98","volume-title":"EurAsia-ICT 2002: Information and Communication Technology","author":"J. D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Ne\u0161et\u0159il, J., Serna, M., Thilikos, D.M.: H-Colorings of Large Degree Graphs. In: Shafazand, H., Tjoa, A.M. (eds.) EurAsia-ICT 2002. LNCS, vol.\u00a02510, pp. 850\u2013857. Springer, Heidelberg (2002)"},{"issue":"1-3","key":"6_CR13","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/0166-218X(93)90222-A","volume":"44","author":"E.S. Elmallah","year":"1993","unstructured":"Elmallah, E.S., Stewart, L.K.: Independence and domination in polygon graphs. Discrete Appllied Math\u00a044(1-3), 65\u201377 (1993)","journal-title":"Discrete Appllied Math"},{"key":"6_CR14","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M. Farber","year":"1985","unstructured":"Farber, M., Keil, J.: Domination in permutation graphs. J. Algorithms\u00a06, 309\u2013321 (1985)","journal-title":"J. Algorithms"},{"issue":"2","key":"6_CR15","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1006\/jctb.2001.2082","volume":"84","author":"J.F. Geelen","year":"2002","unstructured":"Geelen, J.F., Gerards, B., Whittle, G.: Branch-width and well-quasi-ordering in matroids and graphs. J. Comb. Theory, Ser. B\u00a084(2), 270\u2013290 (2002)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-46784-X_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.C. Golumbic","year":"1999","unstructured":"Golumbic, M.C., Rotics, U.: On the Clique-Width of Perfect Graph Classes Extended Abstract. In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 135\u2013147. Springer, Heidelberg (1999)"},{"issue":"40-42","key":"6_CR17","doi-asserted-by":"publisher","first-page":"3601","DOI":"10.1016\/j.tcs.2010.05.041","volume":"411","author":"P. Hof van\u2019t","year":"2010","unstructured":"van\u2019t Hof, P., Paulusma, D., van Rooij, J.M.M.: Computing role assignments of chordal graphs. Theor. Comput. Sci.\u00a0411(40-42), 3601\u20133613 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"6_CR18","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0020-0190(91)90165-E","volume":"40","author":"W.L. Hsu","year":"1991","unstructured":"Hsu, W.L., Tsai, K.H.: Linear time algorithms on circular-arc graphs. Inf. Process. Lett.\u00a040(3), 123\u2013129 (1991)","journal-title":"Inf. Process. Lett."},{"issue":"7","key":"6_CR19","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.dam.2009.02.007","volume":"158","author":"V. Jel\u00ednek","year":"2010","unstructured":"Jel\u00ednek, V.: The rank-width of the square grid. Discrete Applied Math\u00a0158(7), 841\u2013850 (2010)","journal-title":"Discrete Applied Math"},{"issue":"1","key":"6_CR20","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/0166-218X(93)90178-Q","volume":"42","author":"J.M. Keil","year":"1993","unstructured":"Keil, J.M.: The complexity of domination problems in circle graphs. Discrete Applied Math.\u00a042(1), 51\u201363 (1993)","journal-title":"Discrete Applied Math."},{"key":"6_CR21","unstructured":"Kim, K.H.: Boolean matrix theory and its applications. Marcel Dekker (1982)"},{"key":"6_CR22","unstructured":"Kobler, D., Rotics, U.: Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). In: Proc. SODA, pp. 468\u2013476 (2001)"},{"issue":"1","key":"6_CR23","first-page":"41","volume":"2","author":"J. Kratochv\u00edl","year":"1995","unstructured":"Kratochv\u00edl, J., Manuel, P.D., Miller, M.: Generalized domination in chordal graphs. Nord. J. Comput.\u00a02(1), 41\u201350 (1995)","journal-title":"Nord. J. Comput."},{"issue":"6","key":"6_CR24","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0020-0190(94)00159-6","volume":"52","author":"Y. Liang","year":"1994","unstructured":"Liang, Y.: Dominations in trapezoid graphs. Inf. Process. Lett.\u00a052(6), 309\u2013315 (1994)","journal-title":"Inf. Process. Lett."},{"key":"6_CR25","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00453-003-1032-7","volume":"37","author":"R.M. McConnell","year":"2003","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. Algorithmica\u00a037, 93\u2013147 (2003)","journal-title":"Algorithmica"},{"issue":"4","key":"6_CR26","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S. Oum","year":"2006","unstructured":"Oum, S., Seymour, P.D.: Approximating clique-width and branch-width. J. Comb. Theory, Ser. B\u00a096(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"6_CR27","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1137\/S0097539794200383","volume":"25","author":"C. Rhee","year":"1996","unstructured":"Rhee, C., Liang, Y., Dhall, S., Lakshmivarahan, S.: An o(n\u2009+\u2009m)-time algorithm for finding a minimum-weight dominating set in a permutation graph. SIAM J. on Computing\u00a025(2), 404\u2013419 (1996)","journal-title":"SIAM J. on Computing"},{"key":"6_CR28","unstructured":"de Ridder, H.N., et al.: Information System on Graph Classes and their Inclusions (ISGCI), http:\/\/wwwteo.informatik.uni-rostock.de\/isgci"},{"issue":"2","key":"6_CR29","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. X. obstructions to tree-decomposition. J. Comb. Theory, Ser. B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"4","key":"6_CR30","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math.\u00a010(4), 529\u2013550 (1997)","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"6_CR31","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/BF01190158","volume":"9","author":"K.H. Tsai","year":"1993","unstructured":"Tsai, K.H., Hsu, W.L.: Fast algorithms for the dominating set problem on permutation graphs. Algorithmica\u00a09(6), 601\u2013614 (1993)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-25870-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T00:04:51Z","timestamp":1560989091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-25870-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642258695","9783642258701"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-25870-1_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}