{"entities":{"Q2497498":{"pageid":2508241,"ns":120,"title":"Item:Q2497498","lastrevid":44210193,"modified":"2025-11-20T21:19:16Z","type":"item","id":"Q2497498","labels":{"en":{"language":"en","value":"Acyclically pushable bipartite permutation digraphs: an algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5043702"}},"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":"Q2497498$72F24B3F-B19B-430C-B446-317D4F4CBF05","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d1d4eb6ab497b427373e763ceb0eee322abf246","datavalue":{"value":{"text":"Acyclically pushable bipartite permutation digraphs: an algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2497498$991542FE-BD63-4A7E-9EE5-664EBCEB2574","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"946b51f88a5d470305ef350c7793ff611653a7ca","datavalue":{"value":"1098.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$782B4EF5-5D10-46AD-8772-B8FA049126B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"186bb8da4d9a21e884eff28e3a0bd8547b44ac9e","datavalue":{"value":{"entity-type":"item","numeric-id":168651,"id":"Q168651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$1C78F2A0-D909-4A6F-981B-A24E90CBF7EF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$97440FB1-81AB-40F9-B723-56212AB2BB7E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb876cd0509c83d752b9ca15b7a238c782dbf5de","datavalue":{"value":{"time":"+2006-08-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2497498$A5498438-063F-413C-9E29-AF2DBCDC59FF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8efc7824df5537f69345ce9504d4891d430a7223","datavalue":{"value":"Let \\(D(X)\\) denote the digraph obtained from a given digraph \\(D\\) by reversing those arcs with exactly one end in a vertex subset \\(X\\). The digraph \\(D\\) is said to be acyclically pushable when there is an \\(X\\) such that \\(D(X)\\) is acyclic.  The paper gives an algorithmic proof of an early result on characterizing those bipartite permutation digraphs that are acyclically pushable in terms of two excluded induced subgraphs on 7 and 8 vertices. It is claimed that the algorithm can be accomplished in \\(O(mm)\\) time. A strongly acyclic digraph is a digraph \\(D\\) such that \\(D(X)\\) is acyclic for every \\(X\\). It is shown that another early result can be essentially regarded as a characterization of strongly acyclic digraphs. It also provides linear-time algorithms to find a strongly acyclic orientation of an undirected graph, if one exists.   Finally, the paper presents an alternate proof of a theorem on characterizing acyclically pushable bipartite tournaments, leading to a linear-time algorithm, which, given a bipartite tournament as input, either returns a set \\(X\\) such that \\(D(X)\\) is acyclic or a proof that \\(D\\) is not acyclically pushable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497498$197FFB4D-8061-45BC-9551-300958019887","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":"Q2497498$EF81CB05-1634-4892-8E5C-7568BD24F46B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$292B0AA3-46CC-4473-BFC7-11E236ABDF4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$256DDEDA-7476-4210-B93D-E845B9AA68F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$46010398-77D7-465C-9B89-0F8AA32AD983","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"95bb5416c19cebdb416f28758839bd27478dfd31","datavalue":{"value":"5043702","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$5552A9A0-81CA-446A-8377-AA215F3C0A0F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458f12def83c1367a32fd7e7e1dd4b0d57985296","datavalue":{"value":"orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497498$FF0E9630-BD6E-4242-9B27-FAE5B589E050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59334c6473a05b428e26ca729adeca4b06333b71","datavalue":{"value":"push","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497498$9294EDC5-5026-41B5-8087-4BCC241396FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ac6e4320a5ea9b69993de0306e723997ec75d1b","datavalue":{"value":"strongly acyclic digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497498$83B0D953-2CDF-490B-8546-D0A033AB52A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497498$56A4158E-C797-4F4A-8FDC-326B3D17CF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d49cfb1e4c39c6acbfd1e6a37751a0100c25d4","datavalue":{"value":"tournaments","type":"string"},"datatype":"string"},"type":"statement","id":"Q2497498$F9BEA2A3-0A8E-48C7-8106-CCBB47668C01","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":"Q2497498$5EE85E61-C37A-4ADB-A357-9B45A0DD5220","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9de579194d46fd694473b178aaa6c7f2c5d0fb9b","datavalue":{"value":"https://doi.org/10.1016/j.disc.2005.11.027","type":"string"},"datatype":"url"},"type":"statement","id":"Q2497498$749A6734-D3F9-4CB6-BD6B-525019250203","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6fbaa626b8eb43464efa5fba947a13287143cd91","datavalue":{"value":"W1975934581","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$8AFADC3D-5656-4851-BC0A-6ECD35D3C53E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"da45bbbc3d5238fb5aa92c174cbce2d11ecc2564","datavalue":{"value":{"entity-type":"item","numeric-id":1297428,"id":"Q1297428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$E5F422C7-2AA6-4158-84DA-C2146CDBBBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bffe48c7c76b90bf68970921698e19786e1600b","datavalue":{"value":{"entity-type":"item","numeric-id":2747613,"id":"Q2747613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$7F6B9780-609B-4549-87AB-16FAECE4A220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$B59F745E-7BD1-4896-916B-8927F4B6736E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$6AF50859-9F9F-4FCF-B6CC-4A3C8AA2379D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"170c0302cc1fa959b5df2be1c46d06beff8cc702","datavalue":{"value":{"entity-type":"item","numeric-id":5937595,"id":"Q5937595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$617880AF-3EAC-4AFB-BF5B-24262625684A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9faf6b6d0da8ef4698f5035322cdbec5ae17c2e7","datavalue":{"value":{"entity-type":"item","numeric-id":1613399,"id":"Q1613399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$A5D98F80-39C2-4837-A571-DD16BB7916DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"91b64fdbf25968729adccb65c64e4469162d34d1","datavalue":{"value":{"entity-type":"item","numeric-id":2761044,"id":"Q2761044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$D0F319C8-27AB-4A6E-83E0-ACC09B2E673F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8232600f15134b9acbc5fa898aad2f4e89366111","datavalue":{"value":{"entity-type":"item","numeric-id":4242794,"id":"Q4242794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$CC752D31-A185-483E-8029-64FAC540971B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca06c5f09137e8d373da93da4483a14f7be3656e","datavalue":{"value":{"entity-type":"item","numeric-id":2715968,"id":"Q2715968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$CA1D48A7-8BEE-4A71-AC32-8B56F18B2E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5325820f1da9bdbe993d9d54d34a90dc88d69e8e","datavalue":{"value":{"entity-type":"item","numeric-id":4869540,"id":"Q4869540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2497498$07393D23-52AA-4F82-B1BB-3262B24C74C4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4e06b4ba00fc3a5208589b1a9cefefd64dc33975","datavalue":{"value":"10.1016/J.DISC.2005.11.027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2497498$DF88A89E-6F06-4BC1-B50F-D06C3081B16F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f52d30f8c97d68f164daae88969c32159be4c28","datavalue":{"value":{"entity-type":"item","numeric-id":5469725,"id":"Q5469725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd1993698c550e21f5b96ce92f90762177c146d0","datavalue":{"value":{"amount":"+0.9183196","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":"Q2497498$EDA91555-0383-445D-BFF2-1E80DFF622BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63601381c15fea868a31b40f6fb072c11d2500bf","datavalue":{"value":{"entity-type":"item","numeric-id":845701,"id":"Q845701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9aaa4aad6bd365fb14213b92b8826a202009ad47","datavalue":{"value":{"amount":"+0.9028845","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":"Q2497498$2850C7AF-D9F3-44A4-8BD4-1C322AAE4481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fdd717b692349013a1a2d6d4d4112c840ce8b38","datavalue":{"value":{"entity-type":"item","numeric-id":4802252,"id":"Q4802252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cb998b7e32125c856e7904e2aa4f51943353db9","datavalue":{"value":{"amount":"+0.87795603","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":"Q2497498$5F7915C9-657C-47FE-AC4E-7C598EF0825D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dec8ec8f312f01555a418911557a05756bddaf9e","datavalue":{"value":{"entity-type":"item","numeric-id":2329655,"id":"Q2329655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58418a352dc057000d76996e47d8e5c441d7c796","datavalue":{"value":{"amount":"+0.87683445","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":"Q2497498$32D11657-9789-4CE0-9AD0-F6D2A68F68AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a02455b174da99ec5d01677bf1046ae9de29afa","datavalue":{"value":{"entity-type":"item","numeric-id":678867,"id":"Q678867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d1e59b8d3ac4d905f559f314ae168ff72ec536d","datavalue":{"value":{"amount":"+0.8720125","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":"Q2497498$E2041E39-57A8-4AC7-874E-91A22CD9DB90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfaa7f7fcbd233c1f5c3917d35c01507c4d179e3","datavalue":{"value":{"entity-type":"item","numeric-id":5285476,"id":"Q5285476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8eda709506cc98d9066450b5ecbcc665ef3776a","datavalue":{"value":{"amount":"+0.8650669","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":"Q2497498$95939993-AF32-4C9B-8F11-EE4338975FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6153d3d3e1e8edc4a8d16bba1be35c57d23c3277","datavalue":{"value":{"entity-type":"item","numeric-id":1092931,"id":"Q1092931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dc7d22725e6288cb93cba5175604bbdc03895de","datavalue":{"value":{"amount":"+0.86167216","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":"Q2497498$65E77468-2618-43B9-8C17-D8B870DDF7C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1066561f8185f1bab9d26191f08eb8bafac08c7","datavalue":{"value":{"entity-type":"item","numeric-id":4290917,"id":"Q4290917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74841fcae520389bb42bb8cefc66f992026a1027","datavalue":{"value":{"amount":"+0.85956275","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":"Q2497498$3A4FC059-A07E-4986-BC89-81690B16A38A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2497498","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2497498"}}}}}