{"entities":{"Q1613367":{"pageid":1624107,"ns":120,"title":"Item:Q1613367","lastrevid":47976964,"modified":"2026-01-03T06:06:24Z","type":"item","id":"Q1613367","labels":{"en":{"language":"en","value":"A note on transitive orientations with maximum sets of sources and sinks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792315"}},"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":"Q1613367$A392FB4B-32C2-4B6F-AD2D-FD1B1F7855B6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"151282fe16c7e80e70dce6ebb9cf641e12826f78","datavalue":{"value":{"text":"A note on transitive orientations with maximum sets of sources and sinks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613367$DC50E239-9D9D-4EE9-AF14-43F47ADA2C1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"719dfb2d177299570f84c7db500ff048b0d45a10","datavalue":{"value":"1007.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613367$0CC359C0-657D-4118-9590-36FBA781EC22","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5c3d7efb6fc71fba1d097a054f539ea40eef4d2f","datavalue":{"value":"10.1016/S0166-218X(01)00283-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613367$2AEEB3D8-8083-4B65-B410-D9B03D3B51AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$8F9CD01A-10D3-4AC0-8FA5-4355877E1720","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613367$70DF21B5-03D3-43B3-A1FC-088E7EDE659B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"626cb8b8347bc8d2735a30cb542dd6409ff6302c","datavalue":{"value":"Let \\(\\overrightarrow{G}\\) be a transitive orientation of a comparability graph \\(G\\). A vertex in \\(G\\) is called a source (respectively a sink) if its indegree (respectively outdegree) in \\(\\overrightarrow{G}\\) is equal to zero. A pair of subsets \\(S,T\\) of \\(V(G)\\) is a source-sink pair of \\(G\\) if the vertices of \\(S\\) and \\(T\\) are sources and sinks, respectively, of some transitive orientation \\(\\overrightarrow{G}\\) of \\(G\\). The authors prove recurrence equations for computing the maximum cardinality of a source-sink pair, for a given comparability graph. Moreover, they describe a linear-time algorithm that finds a transitive orientation of \\(G\\), for which the source-sink pair achieves the maximum cardinality.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613367$29F3A6FE-040F-4F63-A7A3-1A75297FDF9E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2e24c05a8d3e4c23a551354bc6bd226b3d93e379","datavalue":{"value":{"entity-type":"item","numeric-id":298334,"id":"Q298334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$1C4F9611-8657-49E6-A1F6-D52E16C9A7EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613367$379A6AA7-C8AF-4A31-9EF7-203973EF6267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613367$DFB6150C-591D-4D4A-84B3-7A3DBEEDE597","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7801156f29d4df56b16cb780b1b538e1d4beb05","datavalue":{"value":"1792315","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613367$57C950AE-FA6B-44FA-96E5-4AE113CB573B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5525587197a6d99a1bf5df8093acd4d42b90f196","datavalue":{"value":"comparability graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613367$93D4546D-3EB6-4768-91C6-2E28843D22D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd13113eba663307911e96d64920f6caf0bf316e","datavalue":{"value":"transisive orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613367$365DE34F-8B6C-49CA-9D7D-EEEB28C6A1C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56a4c220e6083c317968a49abbb9dad496c48a25","datavalue":{"value":"source","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613367$C8A8E432-DDDB-4361-9295-772B34D626F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13fa2b59530093ee653224fc65a2a403f97ce633","datavalue":{"value":"sink","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613367$589EB6AC-1D5E-4439-9CD0-073C8F0B1670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613367$0F5F7307-AC0B-4DD3-A061-C8D0B2D3CA00","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8194275e4297e0d41e3cff3373ee47d709a37375","datavalue":{"value":{"entity-type":"item","numeric-id":1567274,"id":"Q1567274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$AEC7D66D-CCEC-4C17-AC95-7B7F300DDA7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca5ab0feaa85889f76115ff5e87e5b62523631d2","datavalue":{"value":{"entity-type":"item","numeric-id":1045054,"id":"Q1045054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$FD423571-0E19-40C5-A7AF-04011432C11D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed1765ff06e31b594da6a4ba93f2dcdf62ea1197","datavalue":{"value":{"entity-type":"item","numeric-id":294686,"id":"Q294686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$36BD9CF1-9E22-4C0F-91FE-3DCE3EF15328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fd683c02639d43389eac3b26f5a1a60d6fdb0bf1","datavalue":{"value":{"entity-type":"item","numeric-id":712274,"id":"Q712274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$0788109D-D97A-4623-BA48-84F11B81231D","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":"Q1613367$80D08F5D-B9E3-49C2-8F69-621DB037A240","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed91ed0176924a73cbecba9388f8a04535563e10","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$D166B163-F9FA-4A0B-839F-D2E06D6085FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ecded16c6af01ba5305fc6d6c5c53e4149b079e","datavalue":{"value":{"entity-type":"item","numeric-id":5501779,"id":"Q5501779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$64DDFB65-8D5F-48EC-8C5C-8E5067C5269B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e092ef189c701e5d39938455a202258a7e3e4a3","datavalue":{"value":{"entity-type":"item","numeric-id":1368667,"id":"Q1368667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$7695B44A-9537-4D6B-82A1-027135836364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97ca141c898326cfe034e4da2d173763055f4264","datavalue":{"value":{"entity-type":"item","numeric-id":3128916,"id":"Q3128916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$2033D5DC-F4DD-4725-8AA4-D86B8D65BF20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a2bbb8ad1f3589516fad98f1995bc229b7720f6","datavalue":{"value":{"entity-type":"item","numeric-id":5501778,"id":"Q5501778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$7B743C6B-FA5D-4222-8C7C-2360332F6C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e405b7fbda3f49c85188dd1e8eaf0b9f0a8ade2b","datavalue":{"value":{"entity-type":"item","numeric-id":1301738,"id":"Q1301738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$CAFC77D0-9EB6-451B-ACBD-0C27B1108FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"565e1c631f28f5626e28b4b72f070c887ee0b094","datavalue":{"value":{"entity-type":"item","numeric-id":3685215,"id":"Q3685215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613367$9B7D4AC7-01AF-4029-83F7-AC724179A1E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"57381b5b0cd2fe96339536961e8e517270298708","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(01)00283-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1613367$955F535F-F743-40E0-9CAE-D6A3CD7428E1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"90e3ed2d9e0af6b4c6e5a88ba30518a8a7cf2388","datavalue":{"value":"W2034559501","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613367$B827EA86-C33A-48EB-85EE-102E0D28E452","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b06376c5b73986c96826e0cc898c09dfda10ad8","datavalue":{"value":{"entity-type":"item","numeric-id":1368667,"id":"Q1368667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f5fde5690df6b225cb586ed123875460391ba8a","datavalue":{"value":{"amount":"+0.8506115078926086","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":"Q1613367$B9080E66-E863-4325-9A36-06B406C39DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd21e1d2dfce3f0749ed5ee0ae4bdb0838098222","datavalue":{"value":{"entity-type":"item","numeric-id":4304381,"id":"Q4304381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dc8b80f56e133420730e68626e5bf9efa3f3a39","datavalue":{"value":{"amount":"+0.8275620937347412","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":"Q1613367$E1A1AC6C-4ADC-4199-B033-60BEFBE743C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43c6bd15fdc799ef36b272636997c99f1efb6c17","datavalue":{"value":{"entity-type":"item","numeric-id":687177,"id":"Q687177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a66feaff5867662536393b1703b60c0dd739dab","datavalue":{"value":{"amount":"+0.8219391107559204","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":"Q1613367$B533A244-1CC5-46CB-AE22-2995F0F628B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbef618e3bd0cb91e237711c0d3f81b704a3f381","datavalue":{"value":{"entity-type":"item","numeric-id":5459137,"id":"Q5459137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23692f37028c5b06830cffff5fd742bcabe70efd","datavalue":{"value":{"amount":"+0.7520378232002258","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":"Q1613367$D3EDC186-AD69-444C-B680-EB93277F349E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95f7a3c63f69e9157a30240be53c0c01a571c442","datavalue":{"value":{"entity-type":"item","numeric-id":3835032,"id":"Q3835032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7d4d38d87aa20136a0f26790a57a24f1b309cce","datavalue":{"value":{"amount":"+0.7475820779800415","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":"Q1613367$EDEEE43B-837F-4A8D-B802-CC0C20440963","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1613367","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1613367"}}}}}