{"entities":{"Q2633178":{"pageid":2643921,"ns":120,"title":"Item:Q2633178","lastrevid":56700678,"modified":"2026-03-19T00:11:32Z","type":"item","id":"Q2633178","labels":{"en":{"language":"en","value":"A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7052053"}},"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":"Q2633178$A49695E9-F904-4F03-8ED3-9FCBD36F6AF1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0dff4219fa3af17e6362a9ef3262d53d6337352c","datavalue":{"value":{"text":"A multi-threading algorithm to detect and remove cycles in vertex- and arc-weighted digraph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2633178$F7358184-FA34-4618-B2D0-2F2DA2DD7BDD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f6384f27f08616f6502f46d9905a2f61517fdbf","datavalue":{"value":"1461.05207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$711C06D4-583D-4DB7-B4FE-84F5D7E4459E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0c168ba96a1527428e163f997119fd6c4b8ad91","datavalue":{"value":{"entity-type":"item","numeric-id":2633175,"id":"Q2633175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$E698F8E9-48DE-4615-9339-A44AC606C678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"243e5a69c4abf04c8f06cfdd559383f302b0cccb","datavalue":{"value":{"entity-type":"item","numeric-id":2633176,"id":"Q2633176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$341687FD-2829-40BF-B1C3-E8D24930871D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"248cc7209f251feaa16f7ff062efe60db59ed445","datavalue":{"value":{"entity-type":"item","numeric-id":2633177,"id":"Q2633177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$7B7BE086-4DE7-4A5B-A047-6CAAF414DD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc09ecf72e7a2359c74aa3ece876772c2528653b","datavalue":{"value":{"entity-type":"item","numeric-id":1750528,"id":"Q1750528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$24A43A77-FA6B-437A-A514-3784317EE464","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":"Q2633178$06F48DB6-D738-46D6-A3CB-84D356D70D5F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8721ec9cf8de43034be561afa7e535bafe3c2e57","datavalue":{"value":{"time":"+2019-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2633178$EDD4F367-2D3F-43A6-BC3C-2740B5834C25","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7bf7843a2ba255740d699c5e13837627c1c57c76","datavalue":{"value":"Summary: A graph is a very important structure to describe many applications in the real world. In many applications, such as dependency graphs and debt graphs, it is an important problem to find and remove cycles to make these graphs be cycle-free. The common algorithm often leads to an out-of-memory exception in commodity personal computer, and it cannot leverage the advantage of multicore computers. This paper introduces a new problem, cycle detection and removal with vertex priority. It proposes a multithreading iterative algorithm to solve this problem for large-scale graphs on personal computers. The algorithm includes three main steps: simplification to decrease the scale of graph, calculation of strongly connected components, and cycle detection and removal according to a pre-defined priority in parallel. This algorithm avoids the out-of-memory exception by simplification and iteration, and it leverages the advantage of multicore computers by multithreading parallelism. Five different versions of the proposed algorithm are compared by experiments, and the results show that the parallel iterative algorithm outperforms the others, and simplification can effectively improve the algorithm's performance.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633178$D4702C13-205B-4ABE-8849-6DB87388094C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$7E64CB31-5EA7-4206-923D-7625EC6E1304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$078F8D1E-D5E7-4DC1-A7BF-E9785344AB4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$D5F19238-A9A9-4C1B-9D92-C10F9FCA4306","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5dd53654bbabadf82c7bdc163b5e25dec151704","datavalue":{"value":"7052053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$8B21D0B9-83A9-438F-8569-668357EFE576","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633178$829A9682-533E-4216-A00D-D658A491F78D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39fc20c798c24c262da32cc2de8c915bfd16905c","datavalue":{"value":"cycle detection and removal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633178$BF71A4EA-C534-4CC9-B8C5-E69D2EE3E1E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"922f4ae9a5a9a013cde55ff49784f9d4ddb8f41f","datavalue":{"value":"vertex- and arc-weighted","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633178$797DE77D-2528-4BD3-8607-C610FB65506A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4ef8ded1c5825ccb2662f5978826acf94644f0d","datavalue":{"value":"multi-threading","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633178$EF2F7909-EF65-401C-AADB-123D61FECBB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b43bf7eef5baa39898efba8eaff82cbeef31aeb2","datavalue":{"value":"iteration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633178$4719E7DE-C756-4613-8E88-0D78A7AE33BC","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8d97611fc0904a05466ed8a98288beb40a9fe79e","datavalue":{"value":{"entity-type":"item","numeric-id":5972514,"id":"Q5972514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$58F2BBC1-AC8B-4EF5-8D19-897FFB0E7FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4f8982fef782754cb5fce4f6379cc62828731503","datavalue":{"value":{"entity-type":"item","numeric-id":25330,"id":"Q25330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$C1CC5BB2-8D96-43E3-BCE8-D5A27512855F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"53f8ba01e34ebb20bac15b4d710887ba18343de9","datavalue":{"value":{"entity-type":"item","numeric-id":27321,"id":"Q27321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$32A72737-A585-425A-9E03-CD713D4759EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"b4014be2188da34f94073b77869226289bd56c5a","datavalue":{"value":{"entity-type":"item","numeric-id":16368,"id":"Q16368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$4961A3D6-60D5-43FF-A16F-F8918551BDC8","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":"Q2633178$2C33B199-BFDE-448D-9877-08C7D4618C66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec9507fd25253050475191a414abe964fb01d9cb","datavalue":{"value":"https://doi.org/10.3390/a10040115","type":"string"},"datatype":"url"},"type":"statement","id":"Q2633178$30375C25-45D6-404B-8D0C-A0393C23BDFA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e84673aff802ad8eb021a68df935dcfae83c2ccf","datavalue":{"value":"W2761683778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$18462162-8F60-4D18-80CB-3972147D257E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"592545e6d067604624b7ea4da4212cd77381242d","datavalue":{"value":{"entity-type":"item","numeric-id":412269,"id":"Q412269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$A022E9F8-4977-4313-B776-5896233EEC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11d21a4724505552412496787b32c5c21064b8ce","datavalue":{"value":{"entity-type":"item","numeric-id":1944201,"id":"Q1944201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$0235D4E9-8280-49FA-9C73-BF03E754BDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"700f5068cbf41662aeafa1cd2d15ca6455ef0124","datavalue":{"value":{"entity-type":"item","numeric-id":5444067,"id":"Q5444067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$04534BC1-33EF-4541-98EF-B7A9DAD628D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59de782bfe9920cc8e3c96207668baaed9f0496e","datavalue":{"value":{"entity-type":"item","numeric-id":274691,"id":"Q274691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$980C9AB7-D06B-4B20-BB5F-54413C6ACE0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6b30a79da2c502d844c366f58179fe092d04530","datavalue":{"value":{"entity-type":"item","numeric-id":274689,"id":"Q274689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$59FC2258-5DED-4697-A74A-5AE5AFAC4F4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1809435900aa4abb4ce083bf2db74d491f63f7c8","datavalue":{"value":{"entity-type":"item","numeric-id":4602855,"id":"Q4602855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$D13AB0E6-CE50-4580-BE3A-02766FAE4734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53fee925c4a46a0d2f8295b6ca87da05c331f44a","datavalue":{"value":{"entity-type":"item","numeric-id":3189043,"id":"Q3189043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$D4FC234A-0E77-49E4-8028-E3597E99A783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acbf68a35efd53fa46006569e2fcabd7e445489d","datavalue":{"value":{"entity-type":"item","numeric-id":4962211,"id":"Q4962211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$8ED0D947-B513-4C70-B6D5-9FBAE9D0956F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90edd91337b9f75f05ada0540fd29f2958b60727","datavalue":{"value":{"entity-type":"item","numeric-id":1062456,"id":"Q1062456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$1455F22E-B3C5-4FAA-A31F-1501DC342069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27f54632faeba316cad1be5af4dc4c700ac87d24","datavalue":{"value":{"entity-type":"item","numeric-id":1990226,"id":"Q1990226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$2AD12585-CE9E-459B-B434-0A1689A4AA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10a9fb51a42039d7abde7fc68a251543d99fdca3","datavalue":{"value":{"entity-type":"item","numeric-id":2484293,"id":"Q2484293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633178$72550A80-519F-413C-8CFB-8149EE388BFF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ee0ced068eacd098cdc54a60de1ff949ab03ebfb","datavalue":{"value":"10.3390/A10040115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633178$78670A99-7156-4CDA-ADAA-D09FDABF3AB2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"899495477496f2f0c44e3c7795cfb7e730eddc48","datavalue":{"value":{"entity-type":"item","numeric-id":910243,"id":"Q910243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5338b279f0223397dcf9b2ee35af8d7f7ad8055","datavalue":{"value":{"amount":"+0.7249453663825989","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":"Q2633178$1B6C0CB1-460F-4B8F-87A3-E1CA428FC1FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc866d0934dd6011c7a82a041ff84faad8c708b0","datavalue":{"value":{"entity-type":"item","numeric-id":4532993,"id":"Q4532993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f869508d191928505477d04dec0d536eb59d5688","datavalue":{"value":{"amount":"+0.6854478120803833","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":"Q2633178$25A22399-CBA0-4413-94B0-36569BCC0031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"370baa9801100b2e07cc7b18dad53e6009944caf","datavalue":{"value":{"entity-type":"item","numeric-id":3046431,"id":"Q3046431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4d5a0fff6190d702fe1b57b1c1906aa571c96bc","datavalue":{"value":{"amount":"+0.6815131306648254","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":"Q2633178$7DE3075F-3156-4E38-9A00-E8CF0BB7994A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e86d60344c3062fdfe29498b8f9754ee5ce2f2b5","datavalue":{"value":{"entity-type":"item","numeric-id":4962211,"id":"Q4962211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2052aeb07d4ff5b19e8182788c5d26f80429495","datavalue":{"value":{"amount":"+0.6804090738296509","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":"Q2633178$2939D361-53E4-411E-AC78-CD79445EF37F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6668ea415f9e0327ab170ca9e816c08b56c53fc1","datavalue":{"value":{"entity-type":"item","numeric-id":3392501,"id":"Q3392501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43ccfd8c798a6e2e191944a372f333b20658c966","datavalue":{"value":{"amount":"+0.6695471405982971","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":"Q2633178$7BC9083D-2C6A-4FED-AF15-1D110E5D3FC7","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":"Q2633178$B8DD5298-CE1F-4B68-A941-29F430AD45A8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2633178","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2633178"}}}}}