{"entities":{"Q5960785":{"pageid":8137587,"ns":120,"title":"Item:Q5960785","lastrevid":58627368,"modified":"2026-04-06T02:00:03Z","type":"item","id":"Q5960785","labels":{"en":{"language":"en","value":"Generating a random sink-free orientation in quadratic time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1730005"}},"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":"Q5960785$B477B608-FFC0-4739-B0FF-48082C9FB3BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8dee6b80130f4f004677135e947cb9dcdf82ca01","datavalue":{"value":{"text":"Generating a random sink-free orientation in quadratic time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5960785$4709E986-FA96-4AE6-B071-135E466DC829","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0edd3d1905c397c3b1e452f7538e0eb3c608e647","datavalue":{"value":"0994.60004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5960785$E165448A-6E24-4EA5-871A-33A941687254","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3d14c941b656d4766ea370aed666dda9e79711d","datavalue":{"value":{"entity-type":"item","numeric-id":241251,"id":"Q241251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5960785$20436EB3-A873-4552-B098-C81ABDF626EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"378da0ceebdbcc7b5d65528a2f725e0a13663ae1","datavalue":{"value":{"entity-type":"item","numeric-id":241252,"id":"Q241252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5960785$23BA5ABD-8699-4224-9A58-D2FD13C2F71B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"051d376d3b77663a61cb93e31ffbc5194d0d18f1","datavalue":{"value":{"entity-type":"item","numeric-id":183298,"id":"Q183298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5960785$1D192FDF-605E-4886-99B1-0D071609DF34","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5960785$BFF87BD3-A378-4022-9346-F94DE3A372F3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"933055a7965477c3a62722623f4f1e3bf21e42c3","datavalue":{"value":{"time":"+2002-04-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5960785$F4D77DB1-776B-4E2A-8FE9-444E062B429C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5120b0aabf970f19e1dbaf608a2a5a543f5bdbcd","datavalue":{"value":"https://arxiv.org/abs/math/0103189","type":"string"},"datatype":"url"},"type":"statement","id":"Q5960785$06F6C285-D90D-4292-B16F-137AB26EED04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"49dea0022815980a37509131d1ad1f9796a507d7","datavalue":{"value":"https://eudml.org/doc/122058","type":"string"},"datatype":"url"},"type":"statement","id":"Q5960785$F2F1958F-EADF-4265-9C14-92A473531D8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a131c05cdee2e26d21874850b5be604992e628ce","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r10.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q5960785$954C1F7C-C47D-4625-A2AB-7990EB0C9E1C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ad9b1d4b500049ebc3dc60605e7af90a0b64052","datavalue":{"value":"Summary: A sink-free orientation of a finite undirected graph is a choice of orientation for each edge such that every vertex has out-degree at least 1. \\textit{R. Bubley} and \\textit{M. Dyer} [in: Proc. 8th Ann. ACM-SIAM Symp. Discrete Algorithms, 248-257 (1997)] used Markov chain Monte Carlo to sample approximately from the uniform distribution on sink-free orientations in time \\(O(m^3 \\log (1 / \\varepsilon))\\), where \\(m\\) is the number of edges and \\(\\varepsilon\\) the degree of approximation. \\textit{M. Huber} [in: Proc. 13th Ann. ACM Symp. Theory Comput., 31-40 (1998)] used coupling from the past to obtain an exact sample in time \\(O(m^4)\\). We present a simple randomized algorithm inspired by Wilson's cycle popping method which obtains an exact sample in mean time at most \\(O(nm)\\), where \\(n\\) is the number of vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5960785$685335F4-8D94-47F3-9317-5DE2D1ADA26F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5960785$70D931E9-5E02-4957-A4E0-6DF0BD78851C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5960785$FDF6BD22-DA3C-4CA1-9693-90F041D531BC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"195a304aefcf5543a21bd19c091c87a9679563a0","datavalue":{"value":"1730005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5960785$FB79F53B-0898-4928-BCCE-CCAE58AAD509","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4b9a7fcbe53b66fea0b5bee39cd62ce927ace4f","datavalue":{"value":"sink-free orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5960785$91654E03-3BEF-49C4-84D4-1A8BEC019363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7e8eecdc1c377e64f81485d4fbc99e14c2691aa","datavalue":{"value":"Markov chain Monte Carlo","type":"string"},"datatype":"string"},"type":"statement","id":"Q5960785$071C15ED-43BB-4B08-A806-77CBDA9A41E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7836b95697763126ce06e8ac5486e8dbccfda202","datavalue":{"value":"coupling from the past","type":"string"},"datatype":"string"},"type":"statement","id":"Q5960785$D70D2C53-B50F-47CD-AA55-29BBD2E570D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b7d70fb041aadb73457b79bc7dc2a8e9b510618","datavalue":{"value":"Wilson's cycle popping method","type":"string"},"datatype":"string"},"type":"statement","id":"Q5960785$148F0896-7CED-422D-B2DD-D872CAA24B3D","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":"Q5960785$2A3EF63F-A2A4-43DD-926C-5D70FEE9C588","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b1e43bb66de74129faec8c27e1780f91b3767c56","datavalue":{"value":"bafkreice3bkmi6ivzb7sf7au5xzuy7zz2bhvpwp36advbguapnzcbpucsi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5960785$241A2531-6ADA-46C8-BEB2-81C64BB2D03C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ccd12fb46ce8edbea499c6eb11a22e0b3d2963","datavalue":{"value":{"entity-type":"item","numeric-id":4542517,"id":"Q4542517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f77570f72b921995a592da09e8676e01e2f5d11","datavalue":{"value":{"amount":"+0.7974938750267029","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":"Q5960785$46EC8135-FAD7-403E-9439-895135D39D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6cf36412f2623c89e8db30b7bfcc9a402260c461","datavalue":{"value":{"entity-type":"item","numeric-id":3154703,"id":"Q3154703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"348a2baf041acc888950a978da83ae2dd178bf19","datavalue":{"value":{"amount":"+0.7741759419441223","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":"Q5960785$C7C9F5F1-6BC6-4A6D-92F5-C5ED2AE6F824","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"998b370436c1c7ce448ec0b96f54b70bc0234119","datavalue":{"value":{"entity-type":"item","numeric-id":4216134,"id":"Q4216134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dad419fc2b11d74bbb83a12e6e20e58b6388f85f","datavalue":{"value":{"amount":"+0.7727824449539185","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":"Q5960785$6894DF35-6107-420F-BD91-ACDA33CDB690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"636353df7c434efecc469d259eec31ad53b95238","datavalue":{"value":{"entity-type":"item","numeric-id":4875218,"id":"Q4875218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba8ac96e9a67d208e671deaed850a335adb2edb2","datavalue":{"value":{"amount":"+0.7607569694519043","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":"Q5960785$FF2E3F08-3088-4985-8615-ECFD72A1A61D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"254bd62a7f6b598411b968f44420c71256ee8524","datavalue":{"value":{"entity-type":"item","numeric-id":2701738,"id":"Q2701738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44ee9895684530d39bd41742caaec4fa33a41baa","datavalue":{"value":{"amount":"+0.7597991824150085","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":"Q5960785$DB80FE38-2CCC-4A20-A9A7-660FCBBFFC91","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5960785","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5960785"}}}}}