{"entities":{"Q802571":{"pageid":804419,"ns":120,"title":"Item:Q802571","lastrevid":48787087,"modified":"2026-01-05T20:54:24Z","type":"item","id":"Q802571","labels":{"en":{"language":"en","value":"Shortest coverings of graphs with cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3891407"}},"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":"Q802571$C87AE802-B45F-4A08-9A62-65B2DB163DAF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46f1455cf7ad15694075686be7218c25548ab2fe","datavalue":{"value":{"text":"Shortest coverings of graphs with cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q802571$C69594F0-9BD6-4999-B63A-332F88A641C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9dcb57f85e3f4411753822a16669a4f21daec62c","datavalue":{"value":"0559.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$08AE3C8C-B15B-479B-960C-F7EC185D788B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"075e5e51351b055c24e1c3573544df28d6e679c3","datavalue":{"value":"10.1016/0095-8956(83)90056-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$7777C6E6-E9B1-4848-890A-C2904BF5971E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6933def1f445e21685d50fc13bd3cfacda780e57","datavalue":{"value":{"entity-type":"item","numeric-id":273170,"id":"Q273170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$761A8BB7-4D6E-4474-8A87-1FB0CFD2B00F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9dbc2e71ff2f0c27bbfd5ad50a72006a7aa52737","datavalue":{"value":{"entity-type":"item","numeric-id":685680,"id":"Q685680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$0ED90F62-235B-4EE3-A5D9-4EDD719E428E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b7589d5ea085f7c1aa012d5ef97abf591210895","datavalue":{"value":{"entity-type":"item","numeric-id":216124,"id":"Q216124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$85E8832F-35B8-44D6-A9E8-5BEAD86EBABA","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$D41AE7AE-B870-486A-904E-85C713777090","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q802571$73D73C59-3B86-4876-94E4-707C4E81792A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d3260dd3a2f1e873616f736d852c5b95ecc8376e","datavalue":{"value":"https://hal.inria.fr/hal-02447197/file/58-BJJ83-coveringcycles.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q802571$7CC5D96D-D0A7-465A-A076-BDB11120F3B9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"36964372fffa1c44f8b28faa096958bed8909a1a","datavalue":{"value":"Es wird bewiesen, da\u00df jeder 2-fach kantenzusammenh\u00e4ngende, endliche Graph G ein System von Kreisen \\(K_ 1,...,K_ m\\) enth\u00e4lt, so da\u00df jede Kante von G zu mindestens einem der Kreise \\(K_ i\\) geh\u00f6rt und \\(\\sum^{m}_{i=1}| K_ i| \\leq \\| G\\| +\\min \\{2/3\\| G\\|,7/3(| G| -1)\\}\\) gilt, wobei \\(| G|\\) bzw. \\(\\| G\\|\\) die Ecken- bzw. Kantenzahl von G bedeute. Dies versch\u00e4rft eine Absch\u00e4tzung aus [\\textit{A. Itai, R. J. Lipton, C. H. Papadimitriou} und \\textit{M. Rodeh}: Covering graphs by simple circuits. SIAM J. Comput. 10, 746-750 (1981; Zbl 0468.68071)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q802571$80DB5902-CCB2-4B81-80C2-873680A0A22A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$7767F371-AC3D-4933-9AE4-09F3BB174E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$7C4FB943-50F3-45A5-87F6-B24AF4DD0DB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$D1F9A494-8C9E-497F-BB90-12D6258D3175","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f63aa54427bc0bb1ff19add2152489241afeec2","datavalue":{"value":"3891407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$33827253-CD94-460A-81A3-51E2A208497B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3faf6cfecc2900df8a26351e696531570f582efe","datavalue":{"value":"edge covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q802571$320F097E-E528-4F17-B833-05DF3AF226C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23489001fcde6a15e45c98c51d0ba11fc009c393","datavalue":{"value":"bridgeless graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q802571$EF8B0597-754F-4C4B-A6B8-5290F9ED15A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q802571$1C6A356B-C536-4886-BAF5-3EB735185A1E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1afc0edb6d4168ab4f0bc093868008629c81e947","datavalue":{"value":{"entity-type":"item","numeric-id":228783,"id":"Q228783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$E19FEC12-08E9-4A59-93E4-3F670C46C8EA","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":"Q802571$3BB9BE41-42CA-489E-B010-0D5B52A07FBB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14a9bb145c1bc6308d5599c88bc018456d7d3c0a","datavalue":{"value":"W1968068042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q802571$A1950399-9F9A-4AEA-AF80-65EBFA584900","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"86187cd049bd6565ddbc4e21f37dc55f378bee76","datavalue":{"value":{"entity-type":"item","numeric-id":1250223,"id":"Q1250223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$268C7744-E2BF-4A96-9F04-CD61F9A4FCA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$7D9F49CB-ECBE-4AA1-B58E-1C2F587BE2F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$453FEE8F-F629-45E4-8A0E-CBC06FEC4329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4679e9667392a96d2459fdcca4f0bdb9ac18ba2f","datavalue":{"value":{"entity-type":"item","numeric-id":5203655,"id":"Q5203655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$0CC1543A-D05D-449F-AA6B-05D10E7931DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd28ee5120155bd6a8313aedd4e9f4b97e5021a0","datavalue":{"value":{"entity-type":"item","numeric-id":5534024,"id":"Q5534024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$9E4C4D9A-0461-43FA-ADB7-B884804DAFA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$A01752E9-C6AC-4359-AA48-9813266B3637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4b70304ff30a1256f46103099164d048b244266","datavalue":{"value":{"entity-type":"item","numeric-id":4766817,"id":"Q4766817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$37DE4CED-3B6C-4AB1-A124-75CEBAC0B4CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"538d8fa5ed3cb10f78591c31223742407791b072","datavalue":{"value":{"entity-type":"item","numeric-id":1233877,"id":"Q1233877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$560E3A00-E860-4802-879D-9B5A74AB544C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d698492d8f1997235ca2ccb391b98cecddc1c730","datavalue":{"value":{"entity-type":"item","numeric-id":1141658,"id":"Q1141658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$59DE10C7-7DBB-4964-BC6E-F0B1D537B83E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"def54ed33f384c86e2a6e6fd0def498d1096930c","datavalue":{"value":{"entity-type":"item","numeric-id":3734435,"id":"Q3734435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$1BAFDE87-5D58-4047-BF3B-3009BAAD0538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19430ad99f365e48b059e51982e7c226f1a136fd","datavalue":{"value":{"entity-type":"item","numeric-id":3922184,"id":"Q3922184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$D255F491-A872-4C95-A109-A765DA4A505E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c528e914f307b3071def0c890dc642f3139474c","datavalue":{"value":{"entity-type":"item","numeric-id":4166786,"id":"Q4166786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$031EF4FB-4EFD-49B0-88CF-58B86BDBB248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e8238df9ba315668607ab8641928fde29b7c57b","datavalue":{"value":{"entity-type":"item","numeric-id":1133552,"id":"Q1133552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$61C464E0-7A3E-4AFA-99F8-077B2BD2D412","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8043dd107c7904927ab042bfc394b0b4d1ce82c4","datavalue":{"value":{"entity-type":"item","numeric-id":4170751,"id":"Q4170751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$98B257AD-2907-48C8-AC54-132D52E2B8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7592de3198c293c7f589e4c11501c8c1996165ef","datavalue":{"value":{"entity-type":"item","numeric-id":5578807,"id":"Q5578807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$393E8601-5177-42FC-A944-DFCA09126C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26df2253b84593db8205883283b4af144b09fcce","datavalue":{"value":{"entity-type":"item","numeric-id":3916595,"id":"Q3916595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q802571$12BF13F4-C335-42E3-9953-E48CEE2D08DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57eca3ad0cbfc766ddd698b0b084c2b04c7fae45","datavalue":{"value":{"entity-type":"item","numeric-id":4030187,"id":"Q4030187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"232d50b53b8024a5ab4406a96d639bafccfea1a6","datavalue":{"value":{"amount":"+0.8183518648147583","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":"Q802571$4331C2C7-F561-4CB6-9C38-B79C01F6DB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09c0003e0a44ab769ecc051cc3c4c4faed3bcbe6","datavalue":{"value":{"entity-type":"item","numeric-id":879941,"id":"Q879941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74ec81cb630914ad0c26ef02dc98c32cd11591f2","datavalue":{"value":{"amount":"+0.8163692951202393","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":"Q802571$C5369D77-E4DA-4085-90CA-3DF26E3716D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3bd3cc3519374feefa9753ff2720ec68e5911eeb","datavalue":{"value":{"entity-type":"item","numeric-id":4284099,"id":"Q4284099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc607b9ffd48afc3d06a77901436fa69b5ea3b24","datavalue":{"value":{"amount":"+0.8112685084342957","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":"Q802571$BE33972B-A4BD-4AD9-8ECE-18F5A289EA59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d4d9c395b655deb1b8c00ba309bf3cc76068dbd","datavalue":{"value":{"entity-type":"item","numeric-id":2213807,"id":"Q2213807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c15805e5df54fdc81afeb89b84bb8b6dc36f356","datavalue":{"value":{"amount":"+0.8109948635101318","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":"Q802571$217CD86C-9AAC-4A64-BCDF-450FE6914686","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76af42a1a24e928f89311aed6e2108a7fadc02c2","datavalue":{"value":{"entity-type":"item","numeric-id":1569041,"id":"Q1569041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb1c501d2bf92236d1cbf4ac64a7fa6ae437f785","datavalue":{"value":{"amount":"+0.8070568442344666","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":"Q802571$8163D251-E89F-4440-95B0-17B5B2F29F5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:802571","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:802571"}}}}}