{"entities":{"Q1273087":{"pageid":1283837,"ns":120,"title":"Item:Q1273087","lastrevid":68348103,"modified":"2026-04-12T23:06:21Z","type":"item","id":"Q1273087","labels":{"en":{"language":"en","value":"A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1229528"}},"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":"Q1273087$5B323A9E-35E6-4C7A-964D-7BFF76A71D22","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"43ef0d0d70b14fffe3eb1677b08b04883cb3cb4a","datavalue":{"value":{"text":"A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1273087$880D5B6F-4689-4A15-BD6E-C16D8D6FE5F6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fd674784a90bf02bcd3070e296090b63fe0541e8","datavalue":{"value":"0920.90137","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1273087$D000829A-5E8D-4D4C-A1D4-6A0E59620815","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e0626105cdfe8ad8281c9687a300d26b8d33a660","datavalue":{"value":"10.1016/S0167-6377(98)00021-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1273087$A7EF1E47-1A9A-4289-8306-453B0266AD08","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c3ff86b1b19eadebada7cfeeabe529384321aa3","datavalue":{"value":{"entity-type":"item","numeric-id":1273086,"id":"Q1273086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$C2FB3AE9-CCC1-4660-BF49-C5893DA4D32E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb42abb4d03c24c0e42c27e662a950bd082fe46","datavalue":{"value":{"entity-type":"item","numeric-id":687041,"id":"Q687041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$09D6BE84-36AF-4816-A3AA-40F2745D59FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5b969806e15667b8bb837290cff38032bdae579d","datavalue":{"value":{"entity-type":"item","numeric-id":242829,"id":"Q242829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$5C107403-85DD-4FF1-856C-FC81D26B3A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac7537c48c812c6b32a62e6d918beaeb90aa1eab","datavalue":{"value":{"entity-type":"item","numeric-id":324760,"id":"Q324760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$BC4995BF-E8BB-4E60-8E8A-7DD9FCCC1ECF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$05B69073-BF8B-4A53-91C6-7AF6370A2305","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"af761311ffae52817306b96effbac921d7df1b38","datavalue":{"value":{"time":"+1999-09-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1273087$06C4F601-988D-4CC2-B4AD-1CDE76AAD8EC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1273087$BF151010-543D-4599-8020-5A2F152EB6EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"195587aee29bc7e4c1826c8e018bc3888a901fb8","datavalue":{"value":"1229528","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1273087$8D10CDFF-5FA8-4D2D-8E9D-10DA5F048C1B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1273087$60F8C817-9B53-4836-A825-2D1B4AECEAD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3c0cc85a0ffe277c732b47c9d97951c2e94bcdd","datavalue":{"value":"2-approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1273087$0E7EFC57-84A9-4C53-A4E5-1DD064BA10B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc032c638ef20db48507160c3aa9ea979ad5af77","datavalue":{"value":"feedback vertex set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1273087$7AA28217-7864-49B2-AA9E-FF821266A995","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"349fe8b51d5e5a4d743195e115d98cccb53f925f","datavalue":{"value":"undirected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1273087$B543C46C-F8FA-4A34-8F04-B07A3423AD38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52cd469b5dffb1e40283107a3df17ff80791ea20","datavalue":{"value":"network design","type":"string"},"datatype":"string"},"type":"statement","id":"Q1273087$91804393-8A87-4D24-8AA2-B420B2462A08","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":"Q1273087$1EBCD7D5-BB34-47A7-8255-227237459245","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba243744d9dbcb7aa0e7e7eb67ab460e4fff84c9","datavalue":{"value":{"entity-type":"item","numeric-id":3128894,"id":"Q3128894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$FBC801B6-CFCB-44A9-BC19-5551C0B9ED55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ef418c941b332926aa9fe4456913c108983bcd1","datavalue":{"value":{"entity-type":"item","numeric-id":2171258,"id":"Q2171258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$2A1412FA-26DF-41D6-A0D5-4CD2D3DBC113","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f79169adfef8be72c6eee8c2d431776df2319966","datavalue":{"value":{"entity-type":"item","numeric-id":4490783,"id":"Q4490783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$780F1F2E-1762-4526-B90E-45D46EBE2EA8","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":"Q1273087$CC2A64F4-6137-4D84-ABDC-32EAF1010600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81b9396aeedff7156ece89f41fe20ace51222bde","datavalue":{"value":{"entity-type":"item","numeric-id":4645920,"id":"Q4645920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$A6FAE571-55A3-4EF9-BF4C-1CF5F81FC697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$CB431351-73DE-4DCD-A7A3-E86F71707E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30e167fa834e4d3d860e2387738463cba17b0f32","datavalue":{"value":{"entity-type":"item","numeric-id":4234131,"id":"Q4234131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$4B2DA39B-BCF2-424F-ABAC-3927DC258371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1db19318df0679c4cfc0681bd7ecd16926445a1","datavalue":{"value":{"entity-type":"item","numeric-id":1900190,"id":"Q1900190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$EEBD7041-EE1E-4DFE-A3D9-A95B7FBCC798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"991f1530881eddfae56657e752d5d0cf43c74224","datavalue":{"value":{"entity-type":"item","numeric-id":6487955,"id":"Q6487955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1273087$575A87FC-9F9D-4821-AB75-F7C129EC4B66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c7ac68ac563ad766db320d2fa8f756d95598b96","datavalue":{"value":{"entity-type":"item","numeric-id":4699157,"id":"Q4699157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a44dc7b1f35dffb0f5084fcff37f5d4110a3839f","datavalue":{"value":{"amount":"+0.9412691","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$25F0A6B6-931B-432F-B380-BC66ADBE5ACF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3be5dd24d915c8f40a1cae93eeb007dca75a05a","datavalue":{"value":{"entity-type":"item","numeric-id":1307344,"id":"Q1307344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"430b26f0ebbfdd21f89a5873f8be97dcf5523ee1","datavalue":{"value":{"amount":"+0.9208219","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$379F903A-91BC-40DD-A9F2-16560370D63A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92113d4bec73ee2b8d727eecbb6d98f00b81455b","datavalue":{"value":{"entity-type":"item","numeric-id":4645920,"id":"Q4645920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"430b26f0ebbfdd21f89a5873f8be97dcf5523ee1","datavalue":{"value":{"amount":"+0.9208219","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$33BD155B-A94C-4C91-B760-1179171EFD16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e26a1843b87e0ab8b059e3649a598f2300284184","datavalue":{"value":{"entity-type":"item","numeric-id":5688508,"id":"Q5688508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c631ba69593531a60f1b84b96a4de13fd94eebf","datavalue":{"value":{"amount":"+0.8968281","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$F4E6B9EE-B02E-4342-9DF9-55186F76E773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bb3cfb8807941b61b4586764d6b4e77f3939b4f","datavalue":{"value":{"entity-type":"item","numeric-id":671377,"id":"Q671377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2890b7624125c6b1fbdbcc34cec7e5d6aeeb05ce","datavalue":{"value":{"amount":"+0.892169","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$E0D2F1DC-7ADE-44BB-A7B6-4C8760D43398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c7295adb30bc6877d5726f530904c6b52b99146","datavalue":{"value":{"entity-type":"item","numeric-id":5919046,"id":"Q5919046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f999b43e8b381fd1ece002c54c2d5a73b4db266","datavalue":{"value":{"amount":"+0.8892456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$F69B5D2E-6AE2-47CE-9329-AC4E7E72241B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07648700dab8c44fedbe5cba2ffaa1e944e888f9","datavalue":{"value":{"entity-type":"item","numeric-id":5896127,"id":"Q5896127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f999b43e8b381fd1ece002c54c2d5a73b4db266","datavalue":{"value":{"amount":"+0.8892456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$C25595B8-0604-40B2-AAE7-A8555E4967AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d04c08bec5d2388153ee063e4afcfe69c6220ba2","datavalue":{"value":{"entity-type":"item","numeric-id":3341924,"id":"Q3341924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46814cb8dc3b72d8daa7079358346f009bc3a136","datavalue":{"value":{"amount":"+0.88646847","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$5DEA9455-4C50-4690-9AA3-395ABC585AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"384a38d228d77008f61fd9a5304db67ef6fde704","datavalue":{"value":{"entity-type":"item","numeric-id":1975362,"id":"Q1975362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c25a078f3a832c2c2285f406c79470a23601a5f","datavalue":{"value":{"amount":"+0.8839178","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$23B6A43C-2225-4406-80AF-E531F4DDB7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5aa7b22420fb1b8ea25a2f2e0384a27df1f0310","datavalue":{"value":{"entity-type":"item","numeric-id":4210077,"id":"Q4210077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a239441a3d24139e735871ffdfdaf840a429532","datavalue":{"value":{"amount":"+0.8823477","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1273087$2541815E-8EEA-4D10-9AAB-7C3A3791DC2E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_primal-dual_interpretation_of_two_2-approximation_algorithms_for_the_feedback_vertex_set_problem_in_undirected_graphs"}}}}}