{"entities":{"Q1102118":{"pageid":1112870,"ns":120,"title":"Item:Q1102118","lastrevid":69955305,"modified":"2026-04-13T11:28:10Z","type":"item","id":"Q1102118","labels":{"en":{"language":"en","value":"Approximation algorithms for weighted matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4049077"}},"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":"Q1102118$808D1221-4784-4439-ABE2-09178EE18787","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"27ae1294b116f3306d959cdae6647b69ea35ebbb","datavalue":{"value":{"text":"Approximation algorithms for weighted matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1102118$1C986B67-44E1-4094-94CF-C0B543ECF13A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df53a07a3a7eba892a660ffa230ca160aef77431","datavalue":{"value":"0643.68084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$30655E52-ABBB-48D4-96E8-F86760DD1E04","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"144960f260f4eb342998bfbfc9418736ee74dcf8","datavalue":{"value":"10.1016/0304-3975(87)90022-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$FDBECEB4-EB83-4869-A544-1B22B3BE7B61","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"02639bdd222cb655d156f9668ee0598e8d62788b","datavalue":{"value":{"entity-type":"item","numeric-id":917566,"id":"Q917566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$48F88A08-E768-4BD8-979A-B3F9AE1F4F01","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$C97798F1-04B8-4C64-BE97-E98A71899399","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1102118$95DCAEB7-C716-4B96-AB54-682D209E2C43","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f0dc7019e9984772236b809fd352525419f3105e","datavalue":{"value":"Approximation algorithms are given for the maximum weighted matching problem in planar and other n-vertex graphs of genus \\(g<n\\). For a planar graph, our approximation runs in O(min\\(\\{\\) (n/\\(\\epsilon)\\)(log n)\\({}^ 2,n/c^{1/\\epsilon}\\})\\) time. For a graph of genus g \\((0<g<n)\\), the running time is \\(O(n^{3/2} \\log n+(g/\\epsilon)n \\log n)\\) time, given a drawing of the graph on a surface of genus g. Here, \\(\\epsilon\\) is the relative error demanded of the approximation and c is a fixed constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102118$638B8DB8-C4CA-491C-9A7A-EACE5656BCA4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$1E07572A-9FE6-4CE2-BB72-9958534EA51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$12605CBA-5C9D-4BB9-8DF9-E5F1C7A48226","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$CCC1AD84-0890-4A33-9822-9185DB0448E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"103a5d1b56383967b62aa519f89c81d202a3d89d","datavalue":{"value":"4049077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$13AB26C4-61EE-4E0B-86F8-A6A323A35EAC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbff35acdd31439d13dd3892bdda5725c18fc300","datavalue":{"value":"Approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102118$FF26ACB0-5A9E-4A01-9ABC-119781564C6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6df988adb2566e4240202e870c727baf856ebaaa","datavalue":{"value":"weighted matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1102118$E29C77E8-8869-4822-9288-4AC58D74AFED","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":"Q1102118$A9409DFA-41E3-49C9-8C2E-07EDAA2A7213","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ae024b3c9606385f2cefd350ef8b2f170bc87d27","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90022-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1102118$1EB1A240-6606-4865-87D5-FFC1DB692CFB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9aefb40d742dd9523d26ef04af8efb6bc7367e6d","datavalue":{"value":"W1998129956","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1102118$ABE74442-59B5-4179-B6B0-13BC815B34D6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0f031f7efbd160d367d8f6b2c9f6a198b07adb9","datavalue":{"value":{"entity-type":"item","numeric-id":3936211,"id":"Q3936211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$6B4EB469-0B74-4481-8AB4-97A7ACD3EC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$AA9550DD-2BEE-4221-92D1-A4456A19B38B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$4C0A6433-3C78-421E-8812-548DF1889677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbb32b7075575c1cb0708f2127f8e393f0d8c07","datavalue":{"value":{"entity-type":"item","numeric-id":3220606,"id":"Q3220606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$662F7A89-DB45-4D5D-8EF5-0E58A2A5B543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03f1ddaba8285217bb41a356c810dd9d4f0f25b5","datavalue":{"value":{"entity-type":"item","numeric-id":5595961,"id":"Q5595961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$808042AB-7BE8-4F11-9DA7-1ABB1D0D1ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$D71DB801-1209-4DDD-B99D-6B18F92FF5C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a2a57b475ae76d5a53ffe9b99df300f7fdeea33","datavalue":{"value":{"entity-type":"item","numeric-id":3906439,"id":"Q3906439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$41E9DE9B-8E57-4056-8FC0-6361DB462856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$83BF38B7-B015-4B93-B43A-C9CBFA29A349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a69a60844867c3ca63f6c08fb5c1f7735796c34","datavalue":{"value":{"entity-type":"item","numeric-id":3922185,"id":"Q3922185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$2D026F10-41F4-4176-A95F-1EF1455967B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72cf3021b0e74c7992b68ece282708ef8d5d3853","datavalue":{"value":{"entity-type":"item","numeric-id":3732963,"id":"Q3732963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1102118$2E9D6D0D-0278-4EDB-AD49-521203587207","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb72d6d874475b5521b4d067c135fb51c5e92f9b","datavalue":{"value":{"entity-type":"item","numeric-id":3732963,"id":"Q3732963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"171c5b7d9235a4b9fea1fbd5b611017bfc12b054","datavalue":{"value":{"amount":"+0.9311671853065492","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":"Q1102118$D374D558-1FDB-4240-9109-51A330AEA886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63ba5aa220fa546eb5045f68c12c1132252c6887","datavalue":{"value":{"entity-type":"item","numeric-id":2944492,"id":"Q2944492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97cb08bad03e4f498756f714774db3acbf229e3e","datavalue":{"value":{"amount":"+0.8916373252868652","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":"Q1102118$96D00903-02B2-48FC-ABD6-526B7460BF1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82df61bb75ae6a11fce91bc302d4b474cb5cd99e","datavalue":{"value":{"entity-type":"item","numeric-id":1007528,"id":"Q1007528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7314a275827e287d10603b5e6efab5cd691873bc","datavalue":{"value":{"amount":"+0.8640863299369812","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":"Q1102118$D3181590-01EA-409B-9A42-4A666E05A544","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"558765ec829db45c20f5e6c8b0cd022c0e7dd4a5","datavalue":{"value":{"entity-type":"item","numeric-id":5900918,"id":"Q5900918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f15e955a7c3292c36188aaa2ba449b295d94125","datavalue":{"value":{"amount":"+0.8566188812255859","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":"Q1102118$3C33F103-BA95-46F5-977A-5AD91C45D5EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e1ee4d0d2027f192aa58b4942bbd95d09b68df4","datavalue":{"value":{"entity-type":"item","numeric-id":4251057,"id":"Q4251057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d935f5ad84e31525361fe67512f54ca7ced7c99d","datavalue":{"value":{"amount":"+0.8542508482933044","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":"Q1102118$DE0A2FAC-7D3D-4D2A-9FE1-98EE67A8F1B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for weighted matching","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_weighted_matching"}}}}}