{"entities":{"Q1736480":{"pageid":1747221,"ns":120,"title":"Item:Q1736480","lastrevid":56686680,"modified":"2026-03-18T20:14:04Z","type":"item","id":"Q1736480","labels":{"en":{"language":"en","value":"Approximating the minimum tour cover of a digraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042099"}},"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":"Q1736480$FFC7C1E5-C46F-41CD-8309-170BAD301B93","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6300a4f30068889d0c2889f55639530ca002cfae","datavalue":{"value":{"text":"Approximating the minimum tour cover of a digraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736480$F6486102-2CD1-4F72-BF80-932809B91142","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae2c0412fecae136fe472a9995975fda01274f3f","datavalue":{"value":"1461.90161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$2ACFB03E-8B42-4900-A93D-DB6C5A7BD20B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3136553beb0b82a888f7886c593b713b30b6e508","datavalue":{"value":{"entity-type":"item","numeric-id":325410,"id":"Q325410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$27EC4CDF-55EF-443F-8087-837B0C4ACDF1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$CCE6FC56-837E-43E4-9B97-598AC559102A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736480$ECE0C91E-40E4-4C60-A7F5-B65188D9CF94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"013409b9596280692762408584be235fb09d63c9","datavalue":{"value":"Summary: Given a directed graph \\(G\\) with non-negative cost on the arcs, a directed tour cover \\(T\\) of \\(G\\) is a cycle (not necessarily simple) in \\(G\\) such that either head or tail (or both of them) of every arc in \\(G\\) is touched by \\(T\\). The minimum directed tour cover problem (DToCP), which is to find a directed tour cover of minimum cost, is \\(NP\\)-hard. It is thus interesting to design approximation algorithms with performance guarantee to solve this problem. Although its undirected counterpart (ToCP) has been studied in recent years, in our knowledge, the DToCP remains widely open. In this paper, we give a \\(2\\log_2(n)\\)-approximation algorithm for the DToCP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736480$0D6DF91D-D4B9-44BE-8386-71A6D2B0B7DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$B3D25429-1B2D-48F2-B422-C7F9522BE5A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$9BC65CCC-E3F9-4C15-9A35-C6BDAACE37CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$606B1253-8556-4CAE-9BF1-627635091549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$859533B6-5B7C-452C-A447-AF0C2E028937","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"997dc15c014fb620b81b92466dcb476931d59be3","datavalue":{"value":"7042099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$DEA517E3-6CA6-4F99-B741-647CFDCB8239","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736480$A0B928AC-C308-4952-B1B2-74C7ADDD5775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a38b11968d7cb86be0842b661cd5bdd713115f5","datavalue":{"value":"graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736480$EEF75439-79D2-4E85-9396-DE4296965B93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07c81530aa969c6eb4163c17dc506fd183ff8f1a","datavalue":{"value":"packing and covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736480$0B266EBE-1157-4D14-9C47-03AA04B64BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d67b0109812de32a2adf0b8607de29086170b8f","datavalue":{"value":"tour cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736480$2DB159AC-4001-4EFC-85EF-197BA839E58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"45600a2ab74acd7b3a4c5e9b8aebf5a6cb61930e","datavalue":{"value":"tree cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736480$971ABA06-13BA-4A14-8C25-3EE99BB802B3","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":"Q1736480$215958DF-54E0-4DAC-8B98-0F8C8FD655AB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a4621ee239b6fe962dd335cd206370f3a2fa0637","datavalue":{"value":"https://doi.org/10.3390/a4020075","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736480$66A77AA0-C9E3-4A56-9F5D-0FF72993D7B1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cded71dd0230853bf1f8f89aee69c0184920add2","datavalue":{"value":"W2004947445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$7ABD3F4A-4F78-40D9-8062-E571B1EB63D2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c28227e02cb5aa673d236d230a232082fd8c5212","datavalue":{"value":{"entity-type":"item","numeric-id":688437,"id":"Q688437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$08FE9238-935F-4236-AC29-70A1800C91CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"537cb3576069c1e54dfdcb8b4f9c36ce2840c760","datavalue":{"value":{"entity-type":"item","numeric-id":1879245,"id":"Q1879245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$3DA32A69-5DAF-4B39-AB57-1879AC841999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e90455869ae5d9f18c15a9aba71c9ea3e755607","datavalue":{"value":{"entity-type":"item","numeric-id":3546300,"id":"Q3546300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$1BF52B64-BAEC-460A-80A8-92256C262D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"095e7239176746db66b05a2150b148f4077bc37d","datavalue":{"value":{"entity-type":"item","numeric-id":3936521,"id":"Q3936521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$415A82BC-86C4-4271-A553-5016D14E654E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"861d68e5ce2f0698135e14e69e8cb3c6d612fdfb","datavalue":{"value":{"entity-type":"item","numeric-id":3138916,"id":"Q3138916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$35B424BE-C972-4332-807B-84205C0D13D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04a8ace826b710cd9d35bd13f7615e7f800d7358","datavalue":{"value":{"entity-type":"item","numeric-id":4103563,"id":"Q4103563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$796DDAEA-7A2A-492F-A7D6-C0121E6DDB37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"759fdcac79b9a44582453742844da0caa96f5fcc","datavalue":{"value":{"entity-type":"item","numeric-id":3794218,"id":"Q3794218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$1E8F8BB0-523E-49CA-A9A9-40915F8644A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5420469b796d83a91c393b7408aa2c45f9960214","datavalue":{"value":{"entity-type":"item","numeric-id":5417632,"id":"Q5417632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$BABB9C04-93C3-49F2-837B-8C8E8853B1C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18db0bd24fad7292566e75bd6e4ff9a6da4100b8","datavalue":{"value":{"entity-type":"item","numeric-id":2861509,"id":"Q2861509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$10B7C928-C026-432D-8A31-38DD178F1560","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"318deabc7d0bde88f27357a75b0b5613a0328334","datavalue":{"value":"10.3390/A4020075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736480$3B261365-959F-41D9-87F4-2320322B773A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"473edddabffd1c89dcfd592cd5906805b23946a6","datavalue":{"value":{"entity-type":"item","numeric-id":688437,"id":"Q688437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"767a5e56cef90ba2a55f4692f620f985175f9f79","datavalue":{"value":{"amount":"+0.91470766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$A892BCA4-E030-4C83-9CD7-670FAD22A147","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"463f50f20561cc0bdadfe00036d8c6f5d343c741","datavalue":{"value":{"entity-type":"item","numeric-id":3192959,"id":"Q3192959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32fa718791b29511f276dca533d8a221965f492c","datavalue":{"value":{"amount":"+0.9096568","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$1CD9ABAF-DB72-465D-B535-117168E8BFDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2b0a4df9463660d5bbe74221a58838347eeace9","datavalue":{"value":{"entity-type":"item","numeric-id":4852628,"id":"Q4852628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53a864455e99a886289eb93eb228f9dda89c3dd0","datavalue":{"value":{"amount":"+0.9077729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$DE8B8A3C-3519-484D-9696-E77D562051B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"152a8669f47a9beb502635181251bb76c1b471f3","datavalue":{"value":{"entity-type":"item","numeric-id":4335208,"id":"Q4335208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53a864455e99a886289eb93eb228f9dda89c3dd0","datavalue":{"value":{"amount":"+0.9077729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$DBEFF0B9-F30E-4BA0-A0B9-6357C7A60B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ddcd05cbe9d92f9588ef52cf9066e88cc7fa1c9","datavalue":{"value":{"entity-type":"item","numeric-id":2258357,"id":"Q2258357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b235ec81fbf674935ddec27525e261c21221f6e2","datavalue":{"value":{"amount":"+0.9070768","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$8A6BCDC6-67EF-4111-8771-19C6C0A473D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48ace6530b844aecb1b188095b5326e45fc82429","datavalue":{"value":{"entity-type":"item","numeric-id":4550498,"id":"Q4550498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"850dc37e320c2625c2199ae0d6fbd5c7b89d9767","datavalue":{"value":{"amount":"+0.89930296","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$B4176FE0-DE99-40B3-A0AF-C83CA910A455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74f7ac6ec0cc9909084e3213ecae18f2545399b4","datavalue":{"value":{"entity-type":"item","numeric-id":4337653,"id":"Q4337653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a028ae3f0d934b83360395e3a39062af6b49a3af","datavalue":{"value":{"amount":"+0.8914404","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$69350B78-C912-4F24-9E9B-425D1AA2E840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45533c16e65c3708c719826e21bf8717b6c16066","datavalue":{"value":{"entity-type":"item","numeric-id":4344209,"id":"Q4344209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06d92be5b263448700cca828bdbc453319e8f7e9","datavalue":{"value":{"amount":"+0.8869597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$843ECF4E-8C65-4044-9F68-5C43D3D0D419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"13964207a605171a257f1af2d069b71a08be5437","datavalue":{"value":{"entity-type":"item","numeric-id":3641922,"id":"Q3641922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1907ca7656f09278121157ce0f579325b14a3b7","datavalue":{"value":{"amount":"+0.8851702","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$7567F154-B995-4002-8804-85EE33359969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"429602dc12afa8860474157e54327fbb97b898cd","datavalue":{"value":{"entity-type":"item","numeric-id":4487449,"id":"Q4487449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dddbd9672d1396eb612a10c7f2389110aaf7e708","datavalue":{"value":{"amount":"+0.8843032","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736480$ACEE1977-E122-4418-96AC-34A64144F996","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736480$012ADABE-E038-4C99-B71F-391927610B64","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736480","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736480"}}}}}