{"entities":{"Q2428634":{"pageid":2439377,"ns":120,"title":"Item:Q2428634","lastrevid":73402047,"modified":"2026-04-14T15:47:46Z","type":"item","id":"Q2428634","labels":{"en":{"language":"en","value":"On the problem of finding disjoint cycles and dicycles in a digraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6028294"}},"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":"Q2428634$38547279-70E6-4B9E-9E0D-C983951A4AF0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"231fa2bc75d0d0d1540fc2cb896f8d8ca5966723","datavalue":{"value":{"text":"On the problem of finding disjoint cycles and dicycles in a digraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2428634$D02B2B60-1D9A-497B-8BAA-EFA2D9B73318","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"74b4045cf216b385a9a1c737bea683ae832a99ba","datavalue":{"value":"1261.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$4A0539C3-EC33-4726-AF84-1250DFA58C80","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bdec8d4d94ee7d0c50419c62c70d19cf4188b751","datavalue":{"value":{"entity-type":"item","numeric-id":345071,"id":"Q345071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$A1A7DB65-19A9-41F4-903F-0A7ED8E196D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f64c4b091272c660c279938fc740575735afef58","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$EC323E5B-72B7-4F82-B843-5A227FE010D1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$1A3EF278-962B-4926-99B2-0DAA0A9764B9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"52b04daa1d703ea977748e4d42defef3819c2dd9","datavalue":{"value":{"time":"+2012-04-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":"Q2428634$1C1FBD6D-1CB3-40FD-BFAD-DB883B649A2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21c9cd4a91dd3b68004ebaf1ca6dab0995107afe","datavalue":{"value":"Given a digraph \\(D\\), the purpose of the paper is to determine whether or not there exist a cycle \\(B\\) in \\(D\\) and a cycle \\(C\\) in its underlying undirected graph \\(UG(D)\\) such that \\(B\\) and \\(C\\) are vertex-disjoint. It is known that the problem is NP-complete if a vertex \\(x\\) is required to be in \\(C\\). In the paper under review it is shown that one can decide the existence of \\(B\\) and \\(C\\) in polynomial time if \\(D\\) is strongly connected. The proposed methods, based on cycle transversal number \\(\\tau(D)\\), actually find \\(B\\) and \\(C\\) in polynomial time if they exist. For \\(\\tau(D)\\) more than 2, the paper uses McCuaig's framework on intercyclic digraphs to find these cycles. For \\(\\tau(D) = 2\\) by using topological methods relying on Thomassen's theorem on 2-linkages in acyclic digraphs, the paper can characterize the digraphs for which the answer is ``yes''. For \\(\\tau(D)\\) less than 2, the paper gives another independent algorithm for its solution.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428634$02F82281-1891-4F5C-B8C5-AC3D74A93E33","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$8F8B2908-AB9A-47C0-9BDC-1AE7B07FDBE4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$9EBCAF62-BC33-44F1-80E7-005C13A62298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$84CB680C-84ED-4960-81FB-18539D03D799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$7F744B2F-5C12-4FF2-B9D5-D7B17ED58216","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"58b5f2057a0339202ef2cbf2d25354561d6301a7","datavalue":{"value":"6028294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$9784D8F6-E49E-4898-9D4E-D0D9889C1891","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fa730215979a24c4645d8813705adab3763e72c","datavalue":{"value":"disjoint cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428634$6EC95280-6533-406B-B5F1-27E75E4B239C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"832ee4ce48dfa60888ebaa21b44469db29be8728","datavalue":{"value":"dicycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428634$8AF6CBA3-675A-4480-88C4-B115CBEF6930","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":"Q2428634$6DCA2834-5A25-4D38-9B32-F68BB4C67A2B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"015340f7a3f27ba42e1ae306f0c47a45d296fe6b","datavalue":{"value":"https://doi.org/10.1007/s00493-011-2670-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q2428634$C42E546B-0BCC-45F3-87C5-D10691D04E42","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d69f39658e5e2e67ac3b1cc5aa14adaa55e9a7d8","datavalue":{"value":"W1988011810","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$3F26F3BC-621D-4446-9CAA-0C2B538C7B9C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$7436100D-9B83-4A13-A55C-74D180011F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84eb93aabfc6acc4b9abb5e1e9322daf161907ac","datavalue":{"value":{"entity-type":"item","numeric-id":1034635,"id":"Q1034635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$CE08409C-79DC-49B2-8462-DD839E6AFF51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70a0003673cca99bcda918db1c0035f694b2d4d6","datavalue":{"value":{"entity-type":"item","numeric-id":5512793,"id":"Q5512793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$4D64C11A-11E2-41A9-8BE7-CC4055F6A162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$4D833263-2B30-4F21-88DD-27E05B9E0E7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b803430208a3c58610291236889c9352f032d419","datavalue":{"value":{"entity-type":"item","numeric-id":5530472,"id":"Q5530472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$F5FE0305-BF31-4C27-A517-59C240E3AD4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b78d94d200e84e5d54e52e6392b8062378f86a34","datavalue":{"value":{"entity-type":"item","numeric-id":4273847,"id":"Q4273847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$82901E3F-F3D4-47BA-9F4E-937541C19EA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd28e5eae24f3b61c09931a700ebfdc24a02edb1","datavalue":{"value":{"entity-type":"item","numeric-id":1325242,"id":"Q1325242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$25B05107-8149-4847-B8DB-A34D4F4342E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"354a350a19b7f023b6db0fa371461b95e5edb9c6","datavalue":{"value":{"entity-type":"item","numeric-id":595675,"id":"Q595675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$464F9552-BD82-4B5B-80FC-17BA9EE5A9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ad3aba62b9edd41da2d3bb0bca2f13b9c46fc14","datavalue":{"value":{"entity-type":"item","numeric-id":1057282,"id":"Q1057282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428634$C497F6C2-3508-446D-A4B3-31CBAD50E407","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e585b3a135b1ba23ca6c06dd187a7b1a68c49bd","datavalue":{"value":"10.1007/S00493-011-2670-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428634$7CCC4EEE-7FEF-47D6-8B01-70D9E4A196C5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf45e4f22ff6a11521c47e553692d5416d47efff","datavalue":{"value":{"entity-type":"item","numeric-id":1307442,"id":"Q1307442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5897ac3e2e6af715d81c67d846c34da71524033","datavalue":{"value":{"amount":"+0.93943924","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":"Q2428634$72424869-5378-47A9-8A03-24A94BA45773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc68552015bd8d0a22b737874b6e094cb111f823","datavalue":{"value":{"entity-type":"item","numeric-id":5205389,"id":"Q5205389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"954ef36cb3630718b10685dc72d7a4e7a23f510b","datavalue":{"value":{"amount":"+0.93822604","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":"Q2428634$0F98F9B5-EADE-4DF8-B978-679B5B537190","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d532863d8a0671eac9070ac725a04e42b3ae3d","datavalue":{"value":{"entity-type":"item","numeric-id":2698538,"id":"Q2698538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbc039e52fcf5348850236631965fd6756dfd14c","datavalue":{"value":{"amount":"+0.91849434","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":"Q2428634$68D89DC7-0EB3-417E-829A-8B51B08948AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba2b99dc123d92a7b0caa0c873ceddd44aa84318","datavalue":{"value":{"entity-type":"item","numeric-id":6081571,"id":"Q6081571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14deb312be87e2c66fcdc9ca1fd229b686b82801","datavalue":{"value":{"amount":"+0.91300964","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":"Q2428634$3652C45F-3ECB-4EA6-947F-DBD8B140CC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91527968bafde6aadaa544f9cb49393ee664ff5a","datavalue":{"value":{"entity-type":"item","numeric-id":1684653,"id":"Q1684653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"046b61ded11729e7e72d879f1aace0fdb08b931c","datavalue":{"value":{"amount":"+0.9127525","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":"Q2428634$5AA8BC26-F209-4CD7-A583-1B407769AF95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffe6fbffafff9b45ff27ef207d30e4a09e94ad4e","datavalue":{"value":{"entity-type":"item","numeric-id":1092919,"id":"Q1092919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17461f0eb81db7b27318fc6d449cc13706d3ee15","datavalue":{"value":{"amount":"+0.91009074","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":"Q2428634$DD5CDB25-5925-4B4D-9DA3-9AB96287A750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a201f22778d3c5b36cccf53ce8dddc9d47c3d79b","datavalue":{"value":{"entity-type":"item","numeric-id":5447600,"id":"Q5447600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"752b0151df0305a71871ef31e06b67ce3ddb5ff2","datavalue":{"value":{"amount":"+0.9076308","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":"Q2428634$766510DC-7F2F-45BA-AAC1-DAA354F3F920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d3a01cc8044670d6e8c7e35c424b70c9cf00a8d","datavalue":{"value":{"entity-type":"item","numeric-id":3439373,"id":"Q3439373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd775558a96f7abf1bb68475ee0b40f7f9feef30","datavalue":{"value":{"amount":"+0.9055577","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":"Q2428634$A7DA953F-5B88-4ACE-BBCC-92322B8F215D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1278cec8a137d699773d323ec937f7b7a058aa09","datavalue":{"value":{"entity-type":"item","numeric-id":3611949,"id":"Q3611949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ee7e8c7e4442a7c3c2a4708577fbece614404ce","datavalue":{"value":{"amount":"+0.90551835","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":"Q2428634$9629C364-B022-4A13-A6C1-3AED7A1D5046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7026030120308c0646f3819c4f935b5508210371","datavalue":{"value":{"entity-type":"item","numeric-id":5883282,"id":"Q5883282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11e0f93a2874e553239fbacbe1d758aabff317ce","datavalue":{"value":{"amount":"+0.9054351","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":"Q2428634$4EA7544C-825B-4DED-B72E-416C1A06E897","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the problem of finding disjoint cycles and dicycles in a digraph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_problem_of_finding_disjoint_cycles_and_dicycles_in_a_digraph"}}}}}