{"entities":{"Q396842":{"pageid":398609,"ns":120,"title":"Item:Q396842","lastrevid":61621809,"modified":"2026-04-11T00:32:27Z","type":"item","id":"Q396842","labels":{"en":{"language":"en","value":"The edit distance function and symmetrization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330298"}},"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":"Q396842$69FB9B26-1E9C-4057-957F-BEBC402CC089","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"bb3025a43ec149f2b0dcf0961c04f260e1af26f4","datavalue":{"value":{"text":"The edit distance function and symmetrization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q396842$0B1756EA-738B-43E9-8058-ADD75B4A22A6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ab06a242c6a6836067b8de1db52ca46281030b44","datavalue":{"value":"1298.05174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396842$0F68D01C-34A4-4611-901B-27525E042D29","rank":"normal"}],"P16":[{"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":"Q396842$5EE10B85-5D9B-4912-912A-83E6460AD1B6","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":"Q396842$EA72E7CA-6292-4D92-A226-BDA10DFB9765","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q396842$33F45944-B650-4C03-AE93-E73EE16271B4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b8bec5a9ad4bb8f05c6b027ba03322e7f234ac3e","datavalue":{"value":"https://arxiv.org/abs/1007.1897","type":"string"},"datatype":"url"},"type":"statement","id":"Q396842$CDD743BA-F2BD-4855-8EA4-35159DD95D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d74282a5016e9c0ebaaced8d1fbd93181384b81","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p26","type":"string"},"datatype":"url"},"type":"statement","id":"Q396842$56789A87-1C6D-4466-B27E-7BD8E22CC5F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f68425b6e1cdf9b32b59efc9d41cfc203bbc932","datavalue":{"value":"Summary: The edit distance between two graphs on the same labeled vertex set is the size of the symmetric difference of the edge sets. The distance between a graph, \\(G\\), and a hereditary property, \\(\\mathbb H\\), is the minimum of the distance between \\(G\\) and each \\(G^\\prime\\in \\mathbb H\\). The edit distance function of \\(\\mathbb H\\) is a function of \\(p\\in[0,1]\\) and is the limit of the maximum normalized distance between a graph of density \\(p\\) and \\(\\mathbb H\\). This paper utilizes a method due to \\textit{A. Sidorenko} [Combinatorica 13, No. 1, 109--120 (1993; Zbl 0774.05051)], called ``symmetrization'', for computing the edit distance function of various hereditary properties. For any graph \\(H\\), \\(\\mathrm{Forb}(H)\\) denotes the property of not having an induced copy of \\(H\\). This paper gives some results regarding estimation of the function for an arbitrary hereditary property. This paper also gives the edit distance function for \\(\\mathrm{Forb}(H)\\), where \\(H\\) is a cycle on 9 or fewer vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$54332309-DEF5-4FE6-9921-E18022D15EAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396842$9BDAB76B-5CFE-4A32-8CE8-1D5979533FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396842$73C3ACCE-E63F-475A-806A-AFFB60F91774","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37652538034c2b03b5609a02d0216e1ceb4dd389","datavalue":{"value":"6330298","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396842$C2CE7DC6-54BF-4587-9AC9-28268BE88B57","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91c92c699214b9d1be7a56f31bd929aa164bb428","datavalue":{"value":"edit distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$0847B811-C09A-48DF-96F0-AB26E200DF24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ff660537c46a0ea02613438ef354efbfd3b43bd","datavalue":{"value":"hereditary properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$E9B0BF0A-32EB-4C23-87CB-08FB37480091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca279b330a109a30d0020ddbdfdb37cb1eb31580","datavalue":{"value":"symmetrization","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$E422B53A-1EEC-467D-AF61-774F6EB7036E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$BF2EB12A-7C85-4CCE-9316-5497949AFA43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7db0e5aa4996908728e8a2fc926cf74690481998","datavalue":{"value":"colored regularity graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$F5FAD989-D06F-4739-AC05-8311F1A6D588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e69e213b51557cc1d7697165bed961e402ad508","datavalue":{"value":"quadratic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q396842$B1630D48-E2EC-4F27-8BC7-4761FE27B4BE","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":"Q396842$DB95D5CF-35FA-4EE6-BB84-CC2BCEAE3597","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c984d6c9728273ad55f676642fad430507e25b8c","datavalue":{"value":{"entity-type":"item","numeric-id":4029804,"id":"Q4029804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$A01F0132-19B4-42A4-AAFF-2BD6D3C77B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363111af09145596e6aa5e7da6afa9e1eeef3376","datavalue":{"value":{"entity-type":"item","numeric-id":3522831,"id":"Q3522831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$F0CDD52D-9933-4539-B990-B5E6F13AD6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04c8333bf8df814384ff78d478592b9e668fdd15","datavalue":{"value":{"entity-type":"item","numeric-id":933672,"id":"Q933672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$451479A9-3EC8-45B2-94C6-48E8201EB958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35cda254a7f7fb453e0c0aaa76f9ca7d98628032","datavalue":{"value":{"entity-type":"item","numeric-id":3652542,"id":"Q3652542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$4129DBF2-2DE4-44DA-8975-DC75D7933E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"032a2cccd6aa7b286288c39dbb930b5a9fce8e89","datavalue":{"value":{"entity-type":"item","numeric-id":1034612,"id":"Q1034612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$04776070-5F10-4E6D-A8F8-FB15356E27BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c451e7676cdd493b5d82e2ca3a9a5cf8a1def560","datavalue":{"value":{"entity-type":"item","numeric-id":3506314,"id":"Q3506314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$3DEFD320-C798-4F61-B4D8-8E65AE9DDD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da233cdbb24b730667b39fdd92d4b7dc2ccc7d95","datavalue":{"value":{"entity-type":"item","numeric-id":5470815,"id":"Q5470815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$4F0F82E0-FA11-4B85-A177-D8F6D6AB4194","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15c11964a2e71cdc829cd58513f856cd5a63935","datavalue":{"value":{"entity-type":"item","numeric-id":1010726,"id":"Q1010726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$6914F38B-57A6-469D-B660-9ECCA9592409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c3f3c18d3012339c8ea8fa516e6cb0de7e130f","datavalue":{"value":{"entity-type":"item","numeric-id":5688999,"id":"Q5688999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$25738C31-A8D5-4719-A06E-6D4EE14AD986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0893f06f165134598a1fdbebb0666712d7a2e96b","datavalue":{"value":{"entity-type":"item","numeric-id":5928567,"id":"Q5928567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$629C5006-92EE-4EA2-8AB7-D1CA6DC95EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"344f697a74f08c27dbfe2d6124ad1eb1876a2d05","datavalue":{"value":{"entity-type":"item","numeric-id":5567713,"id":"Q5567713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$433BA601-6A54-4F91-8630-E662DF45682D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbac1f4f76c6a914430e20bbd6820f01046ec5c3","datavalue":{"value":{"entity-type":"item","numeric-id":3060864,"id":"Q3060864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$670DE062-8457-4B24-A4B1-2C30C5D073FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a912107ca3d203f58f6efc8a1c90b59acfa4be14","datavalue":{"value":{"entity-type":"item","numeric-id":949792,"id":"Q949792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$538FFDDD-D076-4E86-8561-381F059AD279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"212d5478a0d96752f978ca898ec3b53a8bc46b5a","datavalue":{"value":{"entity-type":"item","numeric-id":3970902,"id":"Q3970902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$BFB416C8-53DF-4A97-91C8-81EA5A1CADD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"671f03375ef89e225f597b4e1c3675b819166b8c","datavalue":{"value":{"entity-type":"item","numeric-id":686271,"id":"Q686271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$96ECCD60-A1D0-482A-9001-DB0A2FD9EE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3a2935b025aa7778c170f6093a6202d27fcc2ef","datavalue":{"value":{"entity-type":"item","numeric-id":3989739,"id":"Q3989739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$7411C844-B7D4-4E28-9500-CC148507AA2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d13be61a9265226c3ca5de5861942b79efc09b0f","datavalue":{"value":{"entity-type":"item","numeric-id":2367447,"id":"Q2367447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396842$2F95AD6E-A4B1-4FFC-BFE3-8B4204F3EB4E","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"973f9a33494ec6f113c16f9d043c409fee55380e","datavalue":{"value":"bafkreib56a2ptufbkdn5jwgwgivlb6grl35xulq5mnafkkc4tu3mjh3wwa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396842$CC2A2090-7199-44C8-966A-3A2A09058D36","rank":"normal"}],"P1643":[{"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":"7bfd4f6368b7f3edc850e7e8316a0fb8bc799975","datavalue":{"value":{"amount":"+0.9544031023979188","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":"Q396842$3FB82536-F361-432C-94BE-EA247508529F","rank":"normal"},{"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":"255b936db7350be517a93bbd4ff2c3c0cbab9a97","datavalue":{"value":{"amount":"+0.8970703482627869","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":"Q396842$515EACC3-7BE2-4C43-9B73-28A26B003A06","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":"51a625fadd3788441c2e39c8ba4a6fc0db3054a6","datavalue":{"value":{"amount":"+0.8877323269844055","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":"Q396842$EDDF6CC0-CA1F-4E23-9CF7-048C1C60806B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c1035bd45a351046e455238d1b2a7b74871fe80","datavalue":{"value":{"entity-type":"item","numeric-id":1010726,"id":"Q1010726"},"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":"Q396842$1374BA83-B69B-4095-B4A3-D334DD2F730A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9859dbd987f311b87b8bed2daa97f3627b5573f","datavalue":{"value":{"entity-type":"item","numeric-id":2175239,"id":"Q2175239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b419a8ef448eef4b07d8fdcbe3c33c0d196b9bf","datavalue":{"value":{"amount":"+0.8563197255134583","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":"Q396842$F4068DA1-82D3-4E54-BE70-A395A00C7ED0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The edit distance function and symmetrization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_edit_distance_function_and_symmetrization"}}}}}