{"entities":{"Q1178689":{"pageid":1189438,"ns":120,"title":"Item:Q1178689","lastrevid":66511776,"modified":"2026-04-12T10:34:35Z","type":"item","id":"Q1178689","labels":{"en":{"language":"en","value":"Optimal covering of cacti by vertex-disjoint paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 22281"}},"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":"Q1178689$AB5D6035-AC37-43D3-A27B-03D27F4C1A9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e36c45f3dd6bfb6c7af1f4fdbf8be39109b2ecd3","datavalue":{"value":{"text":"Optimal covering of cacti by vertex-disjoint paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178689$EE30FA9B-B74A-4B21-8977-7CA2EE215078","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9e534a36d20d1efe0451022351bc3e46362cff94","datavalue":{"value":"0741.68082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$31101BC4-7D53-4CD4-B24E-CBA12C1A4A10","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f1c0a88b50bc99dae83007ebe05f2f2215e75602","datavalue":{"value":"10.1016/0304-3975(91)90159-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$76877FD3-78FF-46A6-8D67-3B21338B56C6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3bd4342967813d6c73138a0b6a4a791b0a8c6593","datavalue":{"value":{"entity-type":"item","numeric-id":287984,"id":"Q287984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$5E1F9633-7D48-4976-BE0B-BF183896CC3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea63f93cadd23a193f33dffa78ce5f26a91d7b26","datavalue":{"value":{"entity-type":"item","numeric-id":1095651,"id":"Q1095651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$419D9FF6-519F-4BCF-8408-99379729ED8E","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":"Q1178689$FF969B5E-F591-4AEB-9444-7ACB43C61E59","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-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":"Q1178689$B44CCAC9-B3F9-4AFB-82D0-A7DF06F6543D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"971f54dd8bba56c232e0c7d362d4d9c7f9c829d9","datavalue":{"value":"A graph \\(G\\) is assumed to be undirected, with no loops or parallel edges. A path in \\(G\\) is a sequence of distinct vertices of \\(G\\) such that any two consecutive vertices of the sequence are adjacent in \\(G\\). A path cover of \\(G\\) is a set of vertex-disjoint paths which cover all the vertices of \\(G\\). An optimal cover of \\(G\\) is a path cover of the smallest possible cardinality.   The problem of finding an optimal cover is \\(NP\\)-complete, even for cubic 3-connected planar graph [\\textit{M. Garey}, \\textit{D. Johnson} and \\textit{R. E. Tarjan}, SIAM J. Computing 5, 704-714 (1976; Zbl 0346.05110)]. However, an efficient algorithm for finding an optimal cover of a tree was developed in \\textit{F. T. Boesch}, \\textit{S. Chen} and \\textit{J. A. M. McHugh} [Lect. Notes Math. 406, 201-212 (1974)], and later this result was generalized to graphs in which no two cycles share a vertex [\\textit{S. Pinter} and \\textit{Y. Wolfstahl}, Int. J. Parallel Program. 16(1), 1-15 (1987; Zbl 0632.68029))].   The paper under review generalizes this result further -- to cacti, which are graphs in which no edge lies on more than one cycle. The algorithm derived here runs in linear time in the number of vertices of the input graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178689$2ED44D2A-BE8D-4033-A738-9C50E286F442","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$3B1308E6-7432-4704-B5C8-B7774E60856F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$01917D9C-6738-4501-880B-54EDC0595038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$D4498880-2ED3-4B0B-8FEB-2B9F4D457103","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1a28ff88de3e5b26e69a118597701bb5d3597fa3","datavalue":{"value":"22281","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$A99DA197-0CCE-4553-BE49-C301A36B0F64","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b1406423ed03c0a0bc10028b6422348fbf7b22f","datavalue":{"value":"minimal-cardinality covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178689$1CC7FD24-02EB-4C0D-8390-FE0179BA72FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178689$EFF848CD-1BD8-4B27-A013-F7320F8A3570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be50188cd81901fea93b228767aac63b28c3f1cf","datavalue":{"value":"vertex-disjoint paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178689$86B93B55-7CAA-4FF2-8C8E-AC32449A138C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"902b5ce734ec26a6e1be35c3e5dfd31bcc5f35e5","datavalue":{"value":"cacti","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178689$0C097EEA-F77B-4A55-8A9D-56E446E9DD07","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$039C10EB-20B2-418B-9335-9B514DFCA076","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"45048559eefa05e5e21c6d306ffd9a763129c162","datavalue":{"value":{"entity-type":"item","numeric-id":24801,"id":"Q24801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$4C6912C6-78E9-4D84-AFD8-9F9A9465032D","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":"Q1178689$9CCD810B-0851-4BE7-A167-A890893947ED","rank":"normal"}],"P223":[{"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":"Q1178689$09386058-DD2C-448F-A79A-4984AE99BF28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b8ca49a5619f41a7a3d54dbe6b8ab44e8b6c16","datavalue":{"value":{"entity-type":"item","numeric-id":4052166,"id":"Q4052166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$B9284520-C3D9-4BD4-BB44-101DE16CCA5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f3498f835a6d93e4fa4cac1b62340ea93abfc0","datavalue":{"value":{"entity-type":"item","numeric-id":4132557,"id":"Q4132557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$D5A9A036-7FCB-401C-8AB8-7A22921C17D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cb6d330b0ba17ea9706ff485bd2cc7e5caf6771","datavalue":{"value":{"entity-type":"item","numeric-id":3883524,"id":"Q3883524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$F0924C86-3828-49FE-A1B8-C385C7C27477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18510c5b9d15ee46b96d01656bd46c91c194edde","datavalue":{"value":{"entity-type":"item","numeric-id":4050641,"id":"Q4050641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$25D3C217-65F9-49C8-93F3-48F8FB54D616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2b7958dc2b7884b86126cf911b9071d9ab73aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4115165,"id":"Q4115165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$CD85F873-E785-4377-9B72-F181AC7169D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"986bbfbfdc592691aa35567f34f4fe85a4df458b","datavalue":{"value":{"entity-type":"item","numeric-id":5632589,"id":"Q5632589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$229C019B-F4E8-4326-A82F-F1434AB28837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64c0dc6ac9a731d0a300273973d37f9dfd6057fd","datavalue":{"value":{"entity-type":"item","numeric-id":1095652,"id":"Q1095652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$E5DA8685-E999-4E78-BD01-801886878717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57e71e5b556401efd16915950de24e05b8ad7db1","datavalue":{"value":{"entity-type":"item","numeric-id":4156452,"id":"Q4156452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178689$0A0DEFDC-5751-41F5-8A3D-DA5D21D94A14","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"066f9602e4397de663ee26be66097aeef7b21c74","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90159-y","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178689$8D310E2D-B930-4735-B7D6-1F6EB6AC9CE7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"660b77d64d9b0babe506761e00d2676f145ec0b3","datavalue":{"value":"W2075920437","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178689$2FF799EC-EF8F-4ECD-A241-CA259289A840","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8394e2db52b2cce24a77728b2652f9405ddfe002","datavalue":{"value":{"entity-type":"item","numeric-id":2369003,"id":"Q2369003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46d7a68e909dbe4d26ac932b1bf6b51e74e5108d","datavalue":{"value":{"amount":"+0.8709678053855896","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":"Q1178689$193BA41F-54AF-4E4C-9095-37C02BFF0EBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6ce7b77762b61860655004161721d058041d2df","datavalue":{"value":{"entity-type":"item","numeric-id":1903198,"id":"Q1903198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffad04f4aefde61b51556db13132c515155d35a7","datavalue":{"value":{"amount":"+0.8264822959899902","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":"Q1178689$A27C72AF-547A-4CA8-87CB-26442E140DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33e230489f14504abe720bcc03fbd72a546ba9b9","datavalue":{"value":{"entity-type":"item","numeric-id":1401176,"id":"Q1401176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a1c8206c5f11413bf4cdc26c0011d51aaf6e261","datavalue":{"value":{"amount":"+0.807894229888916","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":"Q1178689$D976D54A-7EE6-4CAA-BDF8-3B0C52617C83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca18dd486c117aec34db9f5058156ffddb4db13e","datavalue":{"value":{"entity-type":"item","numeric-id":1739987,"id":"Q1739987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7b91b1f8279391f317d614a7bab1d11ae4b4c41","datavalue":{"value":{"amount":"+0.8075495958328247","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":"Q1178689$3F69F3DC-6707-43A1-8C24-C576524722F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f46f1c40f8f8d21253f88e542c49b335585d5cb1","datavalue":{"value":{"entity-type":"item","numeric-id":1261472,"id":"Q1261472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dec3810616dd9577613d7ad30b445b8c4f4dd2c4","datavalue":{"value":{"amount":"+0.8058725595474243","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":"Q1178689$FBF9C3CC-2A71-47C6-8CE3-DF63C25EDE64","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal covering of cacti by vertex-disjoint paths","badges":[]}}}}}