{"entities":{"Q2258069":{"pageid":2268812,"ns":120,"title":"Item:Q2258069","lastrevid":71700243,"modified":"2026-04-13T23:58:38Z","type":"item","id":"Q2258069","labels":{"en":{"language":"en","value":"Minimum fill-in of sparse graphs: kernelization and approximation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6410216"}},"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":"Q2258069$185401E7-5425-488B-BCE7-B94BBBDCA5B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4cf1e4c1d1cedad08cdcf041c160ad6b07c16cb6","datavalue":{"value":{"text":"Minimum fill-in of sparse graphs: kernelization and approximation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2258069$F1FD257B-6415-4453-A7C4-AADEC5BB24F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"161ed3e1d2cd51db8d8191fb938720b995c7c084","datavalue":{"value":"1310.68106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$6AE3EBCE-4063-4684-BF07-14B4056F45BF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a8874875f41e100f7dd0c90f8e9a202da131938","datavalue":{"value":{"entity-type":"item","numeric-id":259035,"id":"Q259035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$E152DB55-C457-4DCC-AC82-DCB950680ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e84a38921a493e97609cb06de0bdae9dd6185864","datavalue":{"value":{"entity-type":"item","numeric-id":340564,"id":"Q340564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$EB5B0A0D-49DB-4CCE-9E18-0A64ADBB2AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"61e3255dd787924dbf9a0eadc0fb8e36fab42d95","datavalue":{"value":{"entity-type":"item","numeric-id":315524,"id":"Q315524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$D7E918B7-102C-4C73-BCBF-FC5EFF138A25","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$8A8DA263-8DA6-4614-A15E-8196797DD256","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c1f34cd617859aff4fbe92f8216861e04e26244","datavalue":{"value":{"time":"+2015-03-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2258069$68F6949E-33E8-4003-8036-2B45283F3EF8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"75221949183ca1c65f92ddb3458d2ed8d5efad10","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2011/3345/","type":"string"},"datatype":"url"},"type":"statement","id":"Q2258069$3760A9D8-DED3-4BCE-974B-9EECE4694360","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a0f6294fc45018679af517af32d83b5aa64f41e0","datavalue":{"value":"Given a graph \\(G=(V,E)\\) and a non-negative integer \\(k\\), the Minimum Fill-in problem is to decide if a graph can be triangulated by adding at most \\(k\\) edges. The problem was proved to be NP-complete and there are known its approximation and FPT algorithms. The first and the third author of this paper developed an FPT algorithm for the problem which runs in \\(O(2^{O(\\sqrt k\\log k)}+k^2nm)\\) time.  In this paper the authors develop kernelization algorithms for the problem for several classes of sparse graphs. A kernelization algorithm reduces the input instance down to an instance with size bounded by a polynomial \\(p(k)\\) in \\(k\\) while preserving the answer. I.e., if \\((G, k)\\) is an instance of the Minimum Fill-in problem, the pair \\((G^\\prime, k^\\prime)\\) is a linear kernel if \\(G^\\prime\\) is a graph of size \\(O(k)\\) and there is a fill-in of \\(G\\) with at most \\(k\\) edges if and only if there is a fill-in of \\(G^\\prime\\) with at most \\(k^\\prime\\) edges.  For planar graphs the authors obtain an \\(O(k)\\) kernel, and kernels of size \\(O(k^{3/2})\\) are obtained for graphs excluding some fixed graph as a minor and for graphs of bounded degeneracy. As a byproduct, an approximation algorithm with approximation ratio \\(O(\\log k)\\) on planar graphs and \\(O(\\sqrt k\\log k)\\) on \\(H\\)-minor-free graphs is obtained.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$FC3FDE72-42A3-4A87-A928-735C2E02231D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$D464762C-107A-4931-B9BE-07861EA28A0F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$1E950B73-6379-4916-BD66-3F4A2F059EA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$297D3BCE-CBFC-4EDB-9468-476B7542C328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$7615248E-1CAA-4174-A1CA-1ECBC27CA802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$EF26903A-8466-4C8C-8B4E-ECFC0363FE39","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"beac37c9f0b1f4e446612ceb8c02ff4acb3938d4","datavalue":{"value":"6410216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$A60A1847-FD0E-45C0-A0EF-3FD2E0C22AD0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$B2377B82-8B32-4C25-B023-92AF797BC350","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"040e5cadc2542137fa22dc2efc65268bb08b809c","datavalue":{"value":"kernelization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$3C5D2BEB-2F8E-44D0-8800-87DF9D2025F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7cbd6b65f88f2a70dabe6d23398b760d0f0cee18","datavalue":{"value":"minimum fill-in","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$043E64E8-1B52-4EC5-9EEF-F71A643E3966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$AB1BEE4A-CBE9-4703-97FC-2C2F2574A63D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62d7890861b94e11b88ab74b4da41caf500392f0","datavalue":{"value":"linear kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$C14DECFD-8EA2-46C2-B407-C5C67383D090","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8490ca89a9ab2fa6d58bd76b4316c66d4ce85f3","datavalue":{"value":"\\(d\\)-degenerate graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2258069$99934410-6654-4654-AF73-6070AFA910A2","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":"Q2258069$D3312E84-B352-41E4-896B-1BD2764D4DCE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb1b5ad8e0a3b8d89f87d043b4190cd319a6e762","datavalue":{"value":"W2061643569","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$183287CF-8A55-449F-B4D8-5307E70B2CD5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"da37f9c4389f216438f87d0b5400c829b3573a55","datavalue":{"value":"Q60488431","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$08A197C8-11DA-4E60-AF8B-EC1C9F008D18","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"45d47ec3af3e82ec029533b1d5da20aab651337f","datavalue":{"value":{"entity-type":"item","numeric-id":4288579,"id":"Q4288579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$DECA016A-F581-43DD-9C4C-4046219FE3C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de244e111266d7fc51080d85a58b3c4a69634879","datavalue":{"value":{"entity-type":"item","numeric-id":3583575,"id":"Q3583575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$04FF1BC2-CE01-4E52-8E48-B33FDC2FF899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2f2fe603e72ca9e690f26be9b866cb8b61be0c5","datavalue":{"value":{"entity-type":"item","numeric-id":5468869,"id":"Q5468869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$B144D2FC-9284-4557-9846-7484BA19BDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd8ac350c5bd2d5a17da8118cd84bc5cfa71ac65","datavalue":{"value":{"entity-type":"item","numeric-id":4288578,"id":"Q4288578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$83D6ED7D-75CA-4B15-A0E5-CCDE5D82708A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"935f63010453ad363f6e0c3962ad69169e6022ee","datavalue":{"value":{"entity-type":"item","numeric-id":5171201,"id":"Q5171201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$A5DB4AA7-A9D2-4D82-8C90-A88EADB85C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00267eb49a2b3dae82bc81124fb68ef0764221db","datavalue":{"value":{"entity-type":"item","numeric-id":652537,"id":"Q652537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$52EF5909-7FE2-4343-B9E5-3EBCD0B6F261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c694e31997a7a457bac1c2971d60584b887f7d1","datavalue":{"value":{"entity-type":"item","numeric-id":1352005,"id":"Q1352005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$22E2D92D-8E81-4722-98B2-2F35481F1FA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4a15ea44928931a75acfc912eadee28de71b6e4","datavalue":{"value":{"entity-type":"item","numeric-id":1333327,"id":"Q1333327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$2674259B-E79B-4CBF-B559-936BCD2E220D","rank":"normal"},{"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":"Q2258069$AF177A3B-D671-432E-960A-A9DCBFCB6C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$EA16D3FA-F6B3-4183-81A5-B37E9F91C8E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"befbfe541247817710e22716675e0c030f7b1dfc","datavalue":{"value":{"entity-type":"item","numeric-id":4503944,"id":"Q4503944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$0994D273-AFA0-4A78-82C6-4D55FD30E338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$30E4CF91-75BD-4ED2-B341-BBBCACF4371F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfbbb2cee94289ed36f3fc5baa657d071bdb2993","datavalue":{"value":{"entity-type":"item","numeric-id":5743514,"id":"Q5743514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$94E8F863-2985-469E-B265-55D80C58A537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d11d867708b21942ab74685613391bb9e6ed86f0","datavalue":{"value":{"entity-type":"item","numeric-id":2911621,"id":"Q2911621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$E2B689BD-FF3E-441A-8047-5E166A4706D4","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":"Q2258069$252F4A75-54AE-4206-B6A9-8425D171081B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$A9986FE4-1C5B-4C55-A735-D03D632B3AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d396299693e4f28921602182db43542ab4b6d60","datavalue":{"value":{"entity-type":"item","numeric-id":2519023,"id":"Q2519023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$7EC69D3F-2BFD-4F37-9012-0A672BDB5F31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4534d792f5262a1f297a74f9b43efedcc5cd94ec","datavalue":{"value":{"entity-type":"item","numeric-id":4760022,"id":"Q4760022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$E05A84CE-C019-427E-BFB6-B54047BA8FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c304d846e7c82b77a43d2f603607af265f93ef5","datavalue":{"value":{"entity-type":"item","numeric-id":819823,"id":"Q819823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$6D3710CE-A124-4813-B24A-D7F159ECF795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d451bf1b8f711ef7f538cfdc1a090f03a5a95227","datavalue":{"value":{"entity-type":"item","numeric-id":4268849,"id":"Q4268849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$4A952ECE-D9F8-482C-85BB-E6F31B6419CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3d25b2fcc3945912fd724bc8dcbd801ac846a17","datavalue":{"value":{"entity-type":"item","numeric-id":1392207,"id":"Q1392207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$E81B068E-4AE2-4FB8-9385-7112A7098ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d9e4b22059c0bb3b4aeb7fa4509074ff1f425c6","datavalue":{"value":{"entity-type":"item","numeric-id":4507385,"id":"Q4507385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$BA0159F0-A610-49D1-9CF3-FC947D7AFD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$67113BBD-3698-45C0-B9CE-4FA643B0CEED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf1b2c53ee4a6aaa216a1d0505e15485a1f1842","datavalue":{"value":{"entity-type":"item","numeric-id":1243572,"id":"Q1243572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$A61B7D8F-0EDF-4656-930C-9F88BEE4CE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"246fc69823cd7ad1fedfd2d1c8ea3f8702b26cb8","datavalue":{"value":{"entity-type":"item","numeric-id":1372739,"id":"Q1372739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$B55D5B31-16C3-4F0C-AE9B-A7CF40B95B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79576ab3b16a9292a2f60a1f069d2cdc0ce7bd0f","datavalue":{"value":{"entity-type":"item","numeric-id":3639282,"id":"Q3639282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$3A415E2A-1D6D-494D-AC93-E7BDB7D3AF52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b546b29506726197d486ce9c402fd37a52289738","datavalue":{"value":{"entity-type":"item","numeric-id":5683627,"id":"Q5683627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$6FBD10F3-3FB7-441B-9505-B45DF19E2315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$E631E43E-61DC-48D9-B76D-BF361CA73987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39c83322ec89a0879c019f012ce18dfec20bc796","datavalue":{"value":{"entity-type":"item","numeric-id":1062072,"id":"Q1062072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$E9278A07-2438-459F-91BB-0720E5F51525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed2c50aeb446b65b736ecf15733f4ff471bdc815","datavalue":{"value":{"entity-type":"item","numeric-id":1850528,"id":"Q1850528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$936A253F-92EE-40EE-812D-9B3E7949F312","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20b9c062c65fa50baeb0cadac82aad397e032bf","datavalue":{"value":{"entity-type":"item","numeric-id":3960122,"id":"Q3960122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2258069$C399C80E-D2E1-4CF2-A713-B12A09A4FC21","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0858055322312853b25479b69d48dfc88ee43d0d","datavalue":{"value":"10.1007/S00453-013-9776-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2258069$DE9E3C4B-DC05-4358-8568-74FE83715149","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0d86cc5ab9461db882d34a3406c5dde087205b1","datavalue":{"value":{"entity-type":"item","numeric-id":2911621,"id":"Q2911621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"382e0a3658ee0ade7fc3cd81e3e63ab1169bfa41","datavalue":{"value":{"amount":"+0.9955320358276368","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":"Q2258069$A932A872-DD6D-4212-9F9D-A866743155A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30773b9d1152c146ed2c728c193cd3b14201c6ab","datavalue":{"value":{"entity-type":"item","numeric-id":2304536,"id":"Q2304536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"229c136a951a270c774bc8ac6c9657874d691934","datavalue":{"value":{"amount":"+0.8268789649009705","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":"Q2258069$A68D841D-2969-4B04-BB02-9595FB9F90F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16c21285ce085fc7d6e337b51fc7811411531778","datavalue":{"value":{"entity-type":"item","numeric-id":4575794,"id":"Q4575794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ff37d363d846972744519f35baa2a7b42aaff8e","datavalue":{"value":{"amount":"+0.8247811198234558","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":"Q2258069$B709C134-199F-4D89-8F6C-A29424A3BB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57091da195c404c50c90dd0d60b2977954e8482f","datavalue":{"value":{"entity-type":"item","numeric-id":4507385,"id":"Q4507385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec713d56c0555b05979347c614981b5e275bd001","datavalue":{"value":{"amount":"+0.8232660889625549","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":"Q2258069$E5E8D7F1-90DC-4BB7-9C11-345041EC4183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4607405f69719e94e1c3ef3a43c8e718d4d5351","datavalue":{"value":{"entity-type":"item","numeric-id":2957867,"id":"Q2957867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec713d56c0555b05979347c614981b5e275bd001","datavalue":{"value":{"amount":"+0.8232660889625549","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":"Q2258069$74E69E25-11F2-438C-9C66-E99BCE6DD648","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum fill-in of sparse graphs: kernelization and approximation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_fill-in_of_sparse_graphs:_kernelization_and_approximation"}}}}}