{"entities":{"Q765326":{"pageid":767175,"ns":120,"title":"Item:Q765326","lastrevid":64165689,"modified":"2026-04-11T18:04:40Z","type":"item","id":"Q765326","labels":{"en":{"language":"en","value":"Maximizing edge-ratio is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6015777"}},"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":"Q765326$3970E7E8-A73B-4B8C-AB9C-69198AED6743","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f1c55bc8143d351f96226e09e26d484762149645","datavalue":{"value":{"text":"Maximizing edge-ratio is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q765326$D2FD4674-BD28-4315-8B88-1DBD605B1050","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4d7c59782b3596583abe83451df858b9a94208c","datavalue":{"value":"1408.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$B1BB97FE-425F-460B-9CC6-1B87129BAA1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf5a0e86ee5fc1c6662191d40866b670f7742aee","datavalue":{"value":{"entity-type":"item","numeric-id":412351,"id":"Q412351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$8E7E41B8-E45A-4917-BDC2-AC1F8BEFEE3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bf47db66b00e4c421ce1e7ba44bc0c7e860c19b","datavalue":{"value":{"entity-type":"item","numeric-id":190032,"id":"Q190032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$DAF42969-8E89-4C0B-A62D-EC5509BC1791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"625668ac7c7f497bc8b0ede6424c058cf5bbfd6a","datavalue":{"value":{"entity-type":"item","numeric-id":190033,"id":"Q190033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$9A4510D8-4A2F-4ADB-B684-2DC599E12CF6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$11D32AA0-E7F0-4F19-BDDE-FA918CC151BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e3a09f4fda9fcd4791a88e88ca245a42392f6906","datavalue":{"value":{"time":"+2012-03-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q765326$E2ECF307-EFE5-4D38-9AB1-F5057ABF9256","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$2A4A1673-E5D1-477A-A8FB-F71651B2409E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$88E8B46D-2BAF-46A9-9068-879AC3A43D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$6D5AFDAE-66EA-46DD-94B8-F98FA192F4C7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eeaaef43ddf858458abb04357fc56cbe0fc6639f","datavalue":{"value":"6015777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$3AA029B6-EE4D-4CD3-B58F-4EB2EBFE7D56","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f028273bdeb14266ddfa226da99fbf8ac2a6d27","datavalue":{"value":"graph clustering","type":"string"},"datatype":"string"},"type":"statement","id":"Q765326$83084EA8-EA80-498A-AF04-B337CAE676A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d7db2ee8bcb6619dc340b1da1317f7fbda248b5","datavalue":{"value":"community detection","type":"string"},"datatype":"string"},"type":"statement","id":"Q765326$28EC855F-A5D7-4358-A9B7-D09F1EAF9B51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac0f88351f47809009f5d9cc421a7fb9c3df53fb","datavalue":{"value":"edge-ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q765326$16D41BCF-628F-4B17-B7FA-92811B859846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q765326$55B12668-2E8B-41B8-9C3A-28F5ABDEE231","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":"Q765326$4DCD337B-3868-4BEE-BCC2-2ABF537CEB26","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8fc4f1d81161faf735c49a5ccc1a10641cb76a0c","datavalue":{"value":"https://doi.org/10.1016/j.dam.2011.07.016","type":"string"},"datatype":"url"},"type":"statement","id":"Q765326$F7EF1FAD-B4E4-4563-8988-A0F9CFFA0CD1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"79492d99d7f763c91b74ee241b9d7bc6f6e7541f","datavalue":{"value":"W2055422348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$94C1A925-23B4-4F5B-8A03-4BA14A7F8DE6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$BADEC693-D369-4562-BFEC-78175D99A7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$39069F52-5D6F-4BF0-A4F7-AC01E6B660A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8802396d6d653062718814dd3b9ff34b6644ed58","datavalue":{"value":{"entity-type":"item","numeric-id":3583579,"id":"Q3583579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q765326$6B9B450A-5F65-4C31-8133-311BD427023C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f2a532c5a05d46b5be68953cad4d87cb907eee7e","datavalue":{"value":"10.1016/J.DAM.2011.07.016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q765326$64B5D2EE-CDC1-4250-9403-07F0614FE1C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69973740ba87c86ee4a32cdb639de5d77f3a6a50","datavalue":{"value":{"entity-type":"item","numeric-id":3748301,"id":"Q3748301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dcf9aa40b4b1aa331e18e2a44b0260dca1822a8","datavalue":{"value":{"amount":"+0.7820963859558105","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":"Q765326$65B8F785-9E73-4E79-A0A1-37C73AAFDE01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"297d155f1864a4589ce1d83b18f02997e4603422","datavalue":{"value":{"entity-type":"item","numeric-id":2465958,"id":"Q2465958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bad677da32b8331706c7b81ebe950b547a735ef","datavalue":{"value":{"amount":"+0.7758681774139404","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":"Q765326$C85E7CF2-359D-49F4-9D5B-4F35FC5C9054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d5a121502f8950c75fb6bcfd273c7e34c7acc17","datavalue":{"value":{"entity-type":"item","numeric-id":1210313,"id":"Q1210313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"690caa5bd4b36d3fbb7e9c2d3d2e65e259f5e3a1","datavalue":{"value":{"amount":"+0.7752308249473572","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":"Q765326$2480DB0C-8A9A-410F-9E9B-13233140FEA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"084509a00105518f02df69a4f0259c6c190a79be","datavalue":{"value":{"entity-type":"item","numeric-id":1198051,"id":"Q1198051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"832699f6a55c03fb7e55fe3d33c03d2408c5676a","datavalue":{"value":{"amount":"+0.7739870548248291","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":"Q765326$75B0DF12-1ACB-4F3E-8EA3-27AB26DC6E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17a3614ce0400546cb78f649c19480c8672ea8da","datavalue":{"value":{"entity-type":"item","numeric-id":2254544,"id":"Q2254544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c6cce874dc161ff2d5d0805b3d6be9bec9b83bb","datavalue":{"value":{"amount":"+0.7724477052688599","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":"Q765326$B0EDDF7A-B147-4F80-8C08-247658247FAA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximizing edge-ratio is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximizing_edge-ratio_is_NP-complete"}}}}}