{"entities":{"Q1010726":{"pageid":1012574,"ns":120,"title":"Item:Q1010726","lastrevid":69413997,"modified":"2026-04-13T06:50:23Z","type":"item","id":"Q1010726","labels":{"en":{"language":"en","value":"Edit distance and its computation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540925"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010726$32F1CFB4-E156-4BA3-BA48-84751C63037E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5949db4f702a8f7b8c5463816798b3563f4ab3ee","datavalue":{"value":{"text":"Edit distance and its computation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010726$C0CC8BE9-4009-4156-BF2F-E770FD835F6C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1a3acfcbd6134c9441135ad1e483671fd3e51001","datavalue":{"value":"1159.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010726$8D8E77A8-B4EF-4992-8456-75E4977609D8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9158385d8dfa25fd1cbf34c726849285f5355cf","datavalue":{"value":{"entity-type":"item","numeric-id":189372,"id":"Q189372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010726$D99F0DF9-F257-48FF-9188-32A9B5970BC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15796c0873d9a05767b939c2bba042c56c00920f","datavalue":{"value":{"entity-type":"item","numeric-id":313785,"id":"Q313785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010726$1E6DDE1D-0AA5-499F-B1E0-F63C3B3972C9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010726$412A2DEF-166D-4BD2-9DDD-6EF08810B24C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010726$F4CF02D0-934F-47B4-8C95-6275F5150861","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f0f9220e8dc0a591740ad9b9d128c3fe51e26dcd","datavalue":{"value":"https://arxiv.org/abs/1605.05747","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010726$76C01CAF-75B4-46AD-9E3E-75535DD27D72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d1c03f5314ec37d2cc4084626202974bad6b7833","datavalue":{"value":"https://eudml.org/doc/129764","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010726$528BB025-2617-4440-8BB1-CF38EDA770C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"42e1a9b29063a03947346bd8ac4beba1aa7a9622","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r20.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010726$CA54218A-D37C-43D3-BDB2-B5E26A4B50D2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9de7e57b15444077832f97b7ef35b4a47433f9d2","datavalue":{"value":"Summary: We provide a method for determining the asymptotic value of the maximum edit distance from a given hereditary property. This method permits the edit distance to be computed without using Szemer\u00e9di's Regularity Lemma directly.   Using this new method, we are able to compute the edit distance from hereditary properties for which it was previously unknown. For some graphs \\(H\\), the edit distance from \\(\\text{Forb}(H)\\) is computed, where \\(\\text{Forb}(H)\\) is the class of graphs which contain no induced copy of graph \\(H\\).   Those graphs for which we determine the edit distance asymptotically are \\(H=K_a+E_b\\), an \\(a\\)-clique with \\(b\\) isolated vertices, and \\(H=K_{3,3}\\), a complete bipartite graph. We also provide a graph, the first such construction, for which the edit distance cannot be determined just by considering partitions of the vertex set into cliques and cocliques.   In the process, we develop weighted generalizations of Tur\u00e1n's theorem, which may be of independent interest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010726$B5F79D32-8EDD-49C8-8CEB-8B625FE2661A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010726$9F54EB0A-983D-4251-B35F-3A2A5E358782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010726$9C0BF13C-AD1B-4BE3-A6A7-56501ACD95DB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d6d341439218bc3ed4a10b0f62096690f710cadd","datavalue":{"value":"5540925","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010726$A6ED15C6-6733-4025-BA2B-4A5502C4A4A8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59db80c2b49fde35233aa805f7e38de900f2e27a","datavalue":{"value":"asymptotic value","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010726$EACBC606-2A4C-48B3-BA1C-82E591E438B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f13ef7b7c16a4b9103456bcccde5c5c1aac3e93c","datavalue":{"value":"maximum edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010726$FD254C48-333D-46AA-B3FB-4A01C4E42AEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48da566b96482fc6479bfe499c427d2ce79f9179","datavalue":{"value":"weighted generalization of Turan's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010726$08F8C718-95B0-4A37-9281-D1AFE6C1ABFC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010726$AC2B57B4-EAA1-48B1-BA48-AEF12A191902","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b1978b65d2f71643406c8567288d28b2bc251ea6","datavalue":{"value":"bafkreieyfied2fvemahgzf7s3oj2h3stdmmbjlpdvsszk3nnkcjyw2oase","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010726$33C25A18-372F-44DE-B5B1-FF53BDA8158A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a97b78613a365e88b7c54192b3306ded6e80cb7","datavalue":{"value":{"entity-type":"item","numeric-id":2957174,"id":"Q2957174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f37933070d349dfb980517d44003b35760dddd87","datavalue":{"value":{"amount":"+0.8925507068634033","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010726$7DC89E81-03DC-420D-BEB1-70F8003BB6B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"365ea3c9e7fad702090572f3e0b747595c0fc959","datavalue":{"value":{"entity-type":"item","numeric-id":472982,"id":"Q472982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccc0fd9e94c27f126b8782ef50c92a71cb0c8e31","datavalue":{"value":{"amount":"+0.8820159435272217","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010726$4242E77B-C32C-4DC0-A4E9-E178A023572E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be9cf389f7aaf91b7bec89b3f3d49fe13bacf5bc","datavalue":{"value":{"entity-type":"item","numeric-id":933672,"id":"Q933672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5291771c94e114d803bc30b8053d42159c5d0b36","datavalue":{"value":{"amount":"+0.8812708854675293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010726$77E33F01-4C51-4120-8FA4-BFA17EBAC690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ded1dedd7f281f1023302b7eb98b5f524453a38f","datavalue":{"value":{"entity-type":"item","numeric-id":396842,"id":"Q396842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4d7a084a7278a4a38a981b3e12176d3844d8bb0","datavalue":{"value":{"amount":"+0.8626335263252258","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010726$BCEB00AB-51E6-48A9-AF56-4626EDF0E686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39a0845f8221cf3bff40fbcbc7386168f8b3ac54","datavalue":{"value":{"entity-type":"item","numeric-id":2317648,"id":"Q2317648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"585faa2444570702d035b8a280fae7ec1bbe5958","datavalue":{"value":{"amount":"+0.852014422416687","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1010726$0A7975E0-417C-4F6E-8409-C20FC7BB8691","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Edit distance and its computation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Edit_distance_and_its_computation"}}}}}