{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T00:47:10Z","timestamp":1725756430845},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450426"},{"type":"electronic","value":"9783642450433"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45043-3_16","type":"book-chapter","created":{"date-parts":[[2013,11,12]],"date-time":"2013-11-12T14:05:50Z","timestamp":1384265150000},"page":"177-188","source":"Crossref","is-referenced-by-count":4,"title":["Sparse Square Roots"],"prefix":"10.1007","author":[{"given":"Manfred","family":"Cochefert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Fran\u00e7ois","family":"Couturier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dani\u00ebl","family":"Paulusma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Adamaszek, M.: Uniqueness of graph square roots of girth six. Electr. J. Comb.\u00a018(1) (2011)","DOI":"10.37236\/626"},{"key":"16_CR2","first-page":"223","volume":"54","author":"D. Aingworth","year":"1998","unstructured":"Aingworth, D., Motwani, R., Harary, F.: The difference between a graph and its square. Util. Math.\u00a054, 223\u2013228 (1998)","journal-title":"Util. Math."},{"issue":"6","key":"16_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"16_CR4","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph theory","author":"R. Diestel","year":"2010","unstructured":"Diestel, R.: Graph theory, 4th edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer, Heidelberg (2010)","edition":"4"},{"key":"16_CR5","series-title":"Monographs in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized complexity. Monographs in Computer Science. Springer, New York (1999)"},{"key":"16_CR6","unstructured":"Farzad, B., Karimi, M.: Square-root finding problem in graphs, a complete dichotomy theorem. CoRR abs\/1210.7684 (2012)"},{"issue":"1-2","key":"16_CR7","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00453-010-9442-9","volume":"62","author":"B. Farzad","year":"2012","unstructured":"Farzad, B., Lau, L.C., Le, V.B., Tuy, N.N.: Complexity of finding graph roots with girth conditions. Algorithmica\u00a062(1-2), 38\u201353 (2012)","journal-title":"Algorithmica"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/S0021-9800(68)80079-1","volume":"5","author":"D.P. Geller","year":"1968","unstructured":"Geller, D.P.: The square root of a digraph. J. Combinatorial Theory\u00a05, 320\u2013321 (1968)","journal-title":"J. Combinatorial Theory"},{"issue":"2","key":"16_CR9","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1145\/1150334.1150337","volume":"2","author":"L.C. Lau","year":"2006","unstructured":"Lau, L.C.: Bipartite roots of graphs. ACM Transactions on Algorithms\u00a02(2), 178\u2013208 (2006)","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"16_CR10","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/S0895480103425930","volume":"18","author":"L.C. Lau","year":"2004","unstructured":"Lau, L.C., Corneil, D.G.: Recognizing powers of proper interval, split, and chordal graph. SIAM J. Discrete Math.\u00a018(1), 83\u2013102 (2004)","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"16_CR11","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.disc.2009.09.004","volume":"310","author":"V.B. Le","year":"2010","unstructured":"Le, V.B., Tuy, N.N.: The square of a block graph. Discrete Mathematics\u00a0310(4), 734\u2013741 (2010)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"16_CR12","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.ipl.2010.11.003","volume":"111","author":"V.B. Le","year":"2011","unstructured":"Le, V.B., Tuy, N.N.: A good characterization of squares of strongly chordal split graphs. Inf. Process. Lett.\u00a0111(3), 120\u2013123 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"16_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/S089548019120016X","volume":"8","author":"Y.L. Lin","year":"1995","unstructured":"Lin, Y.L., Skiena, S.: Algorithms for square roots of graphs. SIAM J. Discrete Math.\u00a08(1), 99\u2013118 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"16_CR14","unstructured":"Milanic, M., Schaudt, O.: Computing square roots of trivially perfect and threshold graphs. Discrete Applied Mathematics (in press)"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math.\u00a03, 23\u201328 (1965)","journal-title":"Israel J. Math."},{"issue":"1","key":"16_CR16","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0166-218X(94)00023-9","volume":"54","author":"R. Motwani","year":"1994","unstructured":"Motwani, R., Sudan, M.: Computing roots of graphs is hard. Discrete Applied Mathematics\u00a054(1), 81\u201388 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/S0021-9800(67)80030-9","volume":"2","author":"A. Mukhopadhyay","year":"1967","unstructured":"Mukhopadhyay, A.: The square root of a graph. J. Combinatorial Theory\u00a02, 290\u2013295 (1967)","journal-title":"J. Combinatorial Theory"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1002\/j.1538-7305.1960.tb03936.x","volume":"39","author":"I.C. Ross","year":"1960","unstructured":"Ross, I.C., Harary, F.: The square of a tree. Bell System Tech. J.\u00a039, 641\u2013647 (1960)","journal-title":"Bell System Tech. J."},{"issue":"3","key":"16_CR19","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput.\u00a06(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."}],"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-45043-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,7]],"date-time":"2020-08-07T20:03:29Z","timestamp":1596830609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45043-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450426","9783642450433"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45043-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}