{"entities":{"Q612967":{"pageid":614743,"ns":120,"title":"Item:Q612967","lastrevid":63050568,"modified":"2026-04-11T10:05:47Z","type":"item","id":"Q612967","labels":{"en":{"language":"en","value":"On the uniform generation of modular diagrams"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5827424"}},"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":"Q612967$795181E2-608C-4B50-8294-4AACFA92C6CE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a9a4a475661137e5c363c5998da24f86cbdb4e96","datavalue":{"value":{"text":"On the uniform generation of modular diagrams","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q612967$354DB659-6E68-4E7F-BE61-2F0A4AC06152","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d8afc3a8e342b5a0ed8af70840b88fe0fd389b9c","datavalue":{"value":"1204.05018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612967$1F54B1ED-5158-4CC5-BD80-6A300873E8A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9690eb3737a3086604943e44fd38f145d857872","datavalue":{"value":{"entity-type":"item","numeric-id":172385,"id":"Q172385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612967$CCFFED89-B755-4D8B-8EB2-E153044117FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c8f7afbea44cfd1e8560fa23feb161447506e55","datavalue":{"value":{"entity-type":"item","numeric-id":343071,"id":"Q343071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q612967$DADF5614-D963-42B7-94B0-66F6F7652542","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":"Q612967$D8E1033E-1EBB-4231-A7AD-56392012F657","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63d0db48794e6800d8c22359b1f6c876c0e4d309","datavalue":{"value":{"time":"+2010-12-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q612967$1FE54FF4-50E3-4BB2-8ECF-A8092F1322F3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dfdf9c8827313987c473b0fb55da1ed2d8631b14","datavalue":{"value":"https://arxiv.org/abs/1006.2881","type":"string"},"datatype":"url"},"type":"statement","id":"Q612967$DCC5CFA1-E926-4171-9574-1E5F7B2CE37F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"73cc107b8fc1aa2f9e9f5ab32621e6cc1ccb3ee6","datavalue":{"value":"https://eudml.org/doc/227826","type":"string"},"datatype":"url"},"type":"statement","id":"Q612967$D9FE12B2-888C-409D-8615-A27A398E6FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"94aafae4c6aec4e517abf6f32107488fcbb7a0b3","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r175.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q612967$D4002E9F-9CFE-4AD8-AA00-43C5FC2C1FD3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1a5660d471244559fa19a948a5e4cee3fd49fca1","datavalue":{"value":"Summary: We present an algorithm that generates \\(k\\)-noncrossing, \\(\\sigma\\)-modular diagrams with uniform probability. A diagram is a labeled graph of degree \\(\\leq 1\\) over \\(n\\) vertices drawn in a horizontal line with arcs \\((i,j)\\) in the upper half-plane. A \\(k\\)-crossing in a diagram is a set of \\(k\\) distinct arcs \\((i_1,j_1),(i_2,j_2),\\dots,(i_k,j_k)\\) with the property \\(i_1<i_2<\\cdots<i_k< j_1< j_2<\\cdots< j_k\\). A diagram without any \\(k\\)-crossings is called a \\(k\\)-noncrossing diagram and a stack of length \\(\\sigma\\) is a maximal sequence \\(((i,j), (i+1,j-1),\\dots, (i + (\\sigma-1),j-(\\sigma-1)))\\). A diagram is \\(\\sigma\\)-modular if any arc is contained in a stack of length at least \\(\\sigma\\). Our algorithm generates after \\(O(n^k)\\) preprocessing time, \\(k\\)-noncrossing, \\(\\sigma\\)-modular diagrams in \\(O(n)\\) time and space complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q612967$F3567EAC-68F2-4481-81D5-637F0D8DB2F8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"16a41880afbd8630e6acc78be050f90ea5608911","datavalue":{"value":"05A18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612967$9125CEF9-2CCB-421D-812F-2E190339DA5A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd44caf18df8907519d9cfcd7605d1eecc154854","datavalue":{"value":"5827424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612967$9EAA75E8-1C32-424A-A5C1-7145367232F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dd5edc21cda46734071c8d812269c07a18d8d47","datavalue":{"value":"\\(k\\)-noncrossing diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q612967$BFA47271-F1D5-4A86-B96B-F547D9B1DDF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbccb68ff244ccbcfc8d09e9961d418e11becebd","datavalue":{"value":"uniform generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q612967$B27D8753-531D-41BF-A054-C336047A2AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a695fd0dc6b059447d00a8f5925501f006482f43","datavalue":{"value":"RSK-algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q612967$644C9FB1-6AF2-432B-96C8-095BC6B54500","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":"Q612967$8AFE2E50-991E-4239-8C2A-7018657631F0","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d3ccd3947b79bd84115830bff8835d63f1d24100","datavalue":{"value":"bafkreidrrjwlc6dy5vvaa4v2ywehxysihyrtowsnxhcolhi4gsjn4v7pwa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q612967$7D286280-ED7C-4ED4-B5D0-BDF1EAEC19A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b28faa3a6d9742d2ed55d759e851b33db01f8954","datavalue":{"value":{"entity-type":"item","numeric-id":976735,"id":"Q976735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4028b1621f41990f68fb12128aac319def818e00","datavalue":{"value":{"amount":"+0.8153460621833801","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":"Q612967$0FD7DD71-8F2C-4951-BEDD-55CD9789D62C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"692383606841ff983f85c5c2a94d957abf013f41","datavalue":{"value":{"entity-type":"item","numeric-id":4785701,"id":"Q4785701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"beab079cc1632bc253ec7e945463ff0749ba76bd","datavalue":{"value":{"amount":"+0.7200505137443542","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":"Q612967$9DDC7AC2-2816-4921-85DA-2A50CD7D5B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4391b4906d8e28bf10f259289be7615427f1a779","datavalue":{"value":{"entity-type":"item","numeric-id":982667,"id":"Q982667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"400bb084faceefc4ad16920fa09f39d339ece2e9","datavalue":{"value":{"amount":"+0.7125049233436584","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":"Q612967$2666569D-ADC8-4669-A91E-B184AE30826A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ffb5deed4cbca0b9624cd53bc5ba572ebfb39d5","datavalue":{"value":{"entity-type":"item","numeric-id":4591356,"id":"Q4591356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec78b389677c00695c4ac492fbeb6a2c4e432c9e","datavalue":{"value":{"amount":"+0.7074292302131653","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":"Q612967$293A1693-5C4A-4A3B-A0B4-329127306F6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7a83af692ad37c759aa3e964cbf6e92b7fbb87b","datavalue":{"value":{"entity-type":"item","numeric-id":1010947,"id":"Q1010947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb637d0bbc6391b5ff8cb45615190d4e84468005","datavalue":{"value":{"amount":"+0.699718713760376","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":"Q612967$CC0685D7-DA03-4163-B824-51E850489259","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the uniform generation of modular diagrams","badges":[]}}}}}