{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:11:05Z","timestamp":1725541865659},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642114083"},{"type":"electronic","value":"9783642114090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-11409-0_3","type":"book-chapter","created":{"date-parts":[[2009,12,3]],"date-time":"2009-12-03T13:12:27Z","timestamp":1259845947000},"page":"33-43","source":"Crossref","is-referenced-by-count":0,"title":["A Graph Polynomial Arising from Community Structure (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Ilia","family":"Averbouch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Tittmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.laa.2003.06.010","volume":"377","author":"M. Aigner","year":"2004","unstructured":"Aigner, M., van der Holst, H.: Interlace polynomials. Linear Algebra and Applications\u00a0377, 11\u201330 (2004)","journal-title":"Linear Algebra and Applications"},{"issue":"2","key":"3_CR2","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.1997.1767","volume":"70","author":"A. Andrzejak","year":"1997","unstructured":"Andrzejak, A.: Splitting formulas for Tutte polynomials. Journal of Combinatorial Theory, Series B\u00a070(2), 346\u2013366 (1997)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.jctb.2004.03.003","volume":"92","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollob\u00e1s, B., Sorkin, G.B.: The interlace polynomial of a graph. Journal of Combinatorial Theory, Series B\u00a092, 199\u2013233 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Averbouch, I., Godlin, B., Makowsky, J.A.: The most general edge elimination polynomial (2007), http:\/\/uk.arxiv.org\/pdf\/0712.3112.pdf","DOI":"10.1007\/978-3-540-92248-3_4"},{"key":"3_CR5","unstructured":"Averbouch, I., Godlin, B., Makowsky, J.A.: An extension of the bivariate chromatic polynomial (submitted) (2008)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/978-3-540-73420-8_69","volume-title":"Automata, Languages and Programming","author":"M. Bl\u00e4ser","year":"2007","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the cover polynomial. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 801\u2013812. Springer, Heidelberg (2007)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-79709-8_12","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Bl\u00e4ser","year":"2008","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the Bollob\u00e1s-Riordan polynomia. exceptional points and uniform reductions. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 86\u201398. Springer, Heidelberg (2008)"},{"key":"3_CR8","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. In: STACS, pp. 97\u2013108 (2008)"},{"key":"3_CR9","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, Heidelberg (1999)"},{"key":"3_CR10","unstructured":"Courcelle, B.: Graph Structure and Monadic Second Order Logic. Cambridge University Press, Cambridge (in preparation)"},{"issue":"1-2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second order logic. Discrete Applied Mathematics\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique\u2013width of graphs. Discrete Applied Mathematics\u00a0101, 77\u2013114 (2000)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s00373-003-0534-z","volume":"20","author":"A. Mier de","year":"2004","unstructured":"de Mier, A., Noy, M.: On graphs determined by their Tutte polynomials. Graphs and Combinatorics\u00a020(1), 105\u2013119 (2004)","journal-title":"Graphs and Combinatorics"},{"key":"3_CR14","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198532101.001.0001","volume-title":"Graph Decompositions, A Study in Infinite Graph Theory","author":"R. Diestel","year":"1990","unstructured":"Diestel, R.: Graph Decompositions, A Study in Infinite Graph Theory. Clarendon Press, Oxford (1990)"},{"key":"3_CR15","first-page":"69","volume":"6","author":"K. Dohmen","year":"2003","unstructured":"Dohmen, K., P\u00f6nitz, A., Tittmann, P.: A new two-variable generalization of the chromatic polynomial. Discrete Mathematics and Theoretical Computer Science\u00a06, 69\u201390 (2003)","journal-title":"Discrete Mathematics and Theoretical Computer Science"},{"key":"3_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.F.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"3_CR17","volume-title":"Finite Model Theory","author":"H. Ebbinghaus","year":"1995","unstructured":"Ebbinghaus, H., Flum, J.: Finite Model Theory. Springer, Heidelberg (1995)"},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.dam.2006.06.020","volume":"156","author":"E. Fischer","year":"2008","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree width and clique-width. Discrete Applied Mathematics\u00a0156, 511\u2013529 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR19","doi-asserted-by":"publisher","first-page":"7821","DOI":"10.1073\/pnas.122653799","volume":"99","author":"M. Girvan","year":"2002","unstructured":"Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. Natl. Acad. Sci. USA\u00a099, 7821\u20137826 (2002)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"3_CR20","unstructured":"Godlin, B., Katz, E., Makowsky, J.A.: Graph polynomials: From recursive definitions to subset expansion formulas (2008), http:\/\/uk.arxiv.org\/pdf\/0812.1364.pdf"},{"key":"3_CR21","unstructured":"Hoffmann, C.: A most general edge elimination polynomial\u2013thickening of edges. arXiv:0801.1600v1 [math.CO] (2008)"},{"key":"3_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Phil. Soc.\u00a0108, 35\u201353 (1990)","journal-title":"Math. Proc. Camb. Phil. Soc."},{"issue":"1-3","key":"3_CR23","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Annals of Pure and Applied Logic\u00a0126(1-3), 159\u2013213 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"2","key":"3_CR24","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.dam.2004.01.016","volume":"145","author":"J.A. Makowsky","year":"2005","unstructured":"Makowsky, J.A.: Colored Tutte polynomials and Kauffman brackets on graphs of bounded tree width. Disc. Appl. Math.\u00a0145(2), 276\u2013290 (2005)","journal-title":"Disc. Appl. Math."},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1007\/11780342_35","volume-title":"Logical Approaches to Computational Barriers","author":"J.A. Makowsky","year":"2006","unstructured":"Makowsky, J.A.: From a zoo to a zoology: Descriptive complexity for graph polynomials. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol.\u00a03988, pp. 330\u2013341. Springer, Heidelberg (2006)"},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"J.A. Makowsky","year":"2008","unstructured":"Makowsky, J.A.: From a zoo to a zoology: Towards a general theory of graph polynomials. Theory of Computing Systems\u00a043, 542\u2013562 (2008)","journal-title":"Theory of Computing Systems"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","first-page":"266","volume-title":"Pillars of Computer Science","author":"J.A. Makowsky","year":"2008","unstructured":"Makowsky, J.A., Fischer, E.: Linear recurrence relations for graph polynomials. In: Avron, A., Dershowitz, N., Rabinovich, A. (eds.) Pillars of Computer Science. LNCS, vol.\u00a04800, pp. 266\u2013279. Springer, Heidelberg (2008)"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11917496_18","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"J.A. Makowsky","year":"2006","unstructured":"Makowsky, J.A., Rotics, U., Averbouch, I., Godlin, B.: Computing graph polynomials on graphs of bounded clique-width. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 191\u2013204. Springer, Heidelberg (2006)"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1140\/epjb\/e2004-00124-y","volume":"38","author":"M.E.J. Newman","year":"2004","unstructured":"Newman, M.E.J.: Detecting community structure in networks. Eur. Phys. J.B.\u00a038, 321\u2013330 (2004)","journal-title":"Eur. Phys. J.B."},{"key":"3_CR30","volume-title":"The Structure and Dynamics of Networks","author":"M.E.J. Newman","year":"2006","unstructured":"Newman, M.E.J., Barabasi, A.L., Watts, D.: The Structure and Dynamics of Networks. Princeton University Press, Princeton (2006)"},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1017\/S0963548398003551","volume":"7","author":"S.D. Noble","year":"1998","unstructured":"Noble, S.D.: Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinatorics, Probability and Computing\u00a07, 307\u2013321 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0304-3975(03)00225-1","volume":"307","author":"M. Noy","year":"2003","unstructured":"Noy, M.: On graphs determined by polynomial invariants. TCS\u00a0307, 365\u2013384 (2003)","journal-title":"TCS"},{"key":"3_CR33","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/S0196-8858(03)00088-5","volume":"32","author":"M. Noy","year":"2004","unstructured":"Noy, M., Rib\u00f3, A.: Recursively constructible families of graphs. Advances in Applied Mathematics\u00a032, 350\u2013363 (2004)","journal-title":"Advances in Applied Mathematics"},{"key":"3_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11604686_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Oum","year":"2005","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 49\u201358. Springer, Heidelberg (2005)"},{"key":"3_CR35","first-page":"329","volume-title":"Graph Theory and Related Topics","author":"J.G. Oxley","year":"1979","unstructured":"Oxley, J.G., Welsh, D.J.A.: The Tutte polynomial and percolation. In: Bundy, J.A., Murty, U.S.R. (eds.) Graph Theory and Related Topics, pp. 329\u2013339. Academic Press, London (1979)"},{"key":"3_CR36","unstructured":"Tittmann, P., Averbouch, I., Makowsky, J.A.: The Enumeration of Vertex Induced Subgraphs with Respect to the Number of Components (2009), http:\/\/uk.arxiv.org\/pdf\/0812.4147.pdf (To appear in the European Journal of Combinatorics, 2010)"},{"key":"3_CR37","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0963548303005972","volume":"13","author":"L. Traldi","year":"2004","unstructured":"Traldi, L.: A subset expansion of the coloured Tutte polynomial. Combinatorics, Probability and Computing\u00a013, 269\u2013275 (2004)","journal-title":"Combinatorics, Probability and Computing"},{"key":"3_CR38","doi-asserted-by":"publisher","first-page":"1032","DOI":"10.1016\/j.dam.2005.09.013","volume":"6","author":"L. Traldi","year":"2006","unstructured":"Traldi, L.: On the colored Tutte polynomial of a graph of bounded tree-width. Discrete Applied Mathematics\u00a06, 1032\u20131036 (2006)","journal-title":"Discrete Applied Mathematics"}],"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-11409-0_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,17]],"date-time":"2024-03-17T23:58:33Z","timestamp":1710719913000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-11409-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642114083","9783642114090"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11409-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}