{"entities":{"Q2761044":{"pageid":2771783,"ns":120,"title":"Item:Q2761044","lastrevid":41982302,"modified":"2025-05-20T12:33:03Z","type":"item","id":"Q2761044","labels":{"en":{"language":"en","value":"Pushing vertices and orienting edges"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1682906"}},"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":"Q2761044$6C48BA10-39C6-46AC-B461-9B052FF2F7CE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f87b165d2714446fc92f7b29a0f503e0b0ceae6","datavalue":{"value":"0977.05057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761044$45B12E43-6DEC-4C67-AFCF-543CB0A06367","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0e5df302565d2de1eeef2fcdc9afdeee5289ecc","datavalue":{"value":{"entity-type":"item","numeric-id":335332,"id":"Q335332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761044$6760EF28-0787-45BA-9ACA-4FC00DF4FC83","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dd43b7556960d36e19e31bfdf153901cadf12bc7","datavalue":{"value":{"time":"+2001-12-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2761044$9C7C76FE-ADD8-497A-BBA0-8771DEF65C8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761044$E2F83355-D031-4962-A238-3176E3C30280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761044$4EB41BC8-AD62-4582-AB74-5CF3CA8EAB37","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d762bab127083c7e8379a45f81a8bd8cc19df02","datavalue":{"value":"1682906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2761044$8488537B-EFFF-49C0-B6FD-8290056C0507","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bd42ff80b8dded5eb2e73909fb602881916a4db2","datavalue":{"value":"pushing a vertex","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761044$09E90A99-DCBD-4609-8814-D214447C16DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23327429ccc9c4db577944943301140158871dad","datavalue":{"value":"reverse orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761044$64A94464-29AE-467C-AB21-C7D0C0BD9057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffa219ea2cff89df5162edb57bd2a31ea73e1a26","datavalue":{"value":"digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761044$AA3DA0A3-4400-4748-951A-1493510531C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d49cfb1e4c39c6acbfd1e6a37751a0100c25d4","datavalue":{"value":"tournaments","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761044$A791E4B4-63F4-4773-9B13-9E7A4374D5AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761044$80C8A785-07F5-450E-BB33-3911A14917CB","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":"Q2761044$99C96105-9550-45DB-ADFB-5D97A587A3D4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57c7aabd40040378759577e086b849000c60ffa3","datavalue":{"value":{"entity-type":"item","numeric-id":5959552,"id":"Q5959552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"681e120f416d974f4af028e7ff9ddf49b07f1892","datavalue":{"value":{"amount":"+0.86981577","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":"Q2761044$FF9E6C95-DD29-4151-8A69-F93288A35958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b7b6f5e83d472e02d87fa5b70d0ee3b48235837","datavalue":{"value":{"entity-type":"item","numeric-id":4458214,"id":"Q4458214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c86c753593a44e56e396fa687d2e9c6c08003141","datavalue":{"value":{"amount":"+0.86206865","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":"Q2761044$D9D1D49B-17AA-4C3C-84C2-621A21AF4A52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cadd4704ce0f21c634f21e7e4a675a844744c7a","datavalue":{"value":{"entity-type":"item","numeric-id":2833256,"id":"Q2833256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05f6cdf6ebf3574fff4739f1d68622a219f93cea","datavalue":{"value":{"amount":"+0.82045144","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":"Q2761044$4C17B175-15FA-4304-86E5-FFACE7CC410E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5535d67092821441fc2c631404a35918bc45a35b","datavalue":{"value":{"entity-type":"item","numeric-id":1807608,"id":"Q1807608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9dd24281f92feb3aa86502f791ccded217cde9f","datavalue":{"value":{"amount":"+0.8140892","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":"Q2761044$411C458E-625C-47BD-A596-E1E321204BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8abce4e98e0ba0a3ece07514dbefaab994ddde29","datavalue":{"value":{"entity-type":"item","numeric-id":4839495,"id":"Q4839495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec8dff5ff935384421e49e929840efe691087834","datavalue":{"value":{"amount":"+0.8127893","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":"Q2761044$1FE2B789-8FE2-4C93-BED1-BB9ADD275F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cccce19e309c7e05d833cf98489709a30e0dd3f5","datavalue":{"value":{"entity-type":"item","numeric-id":5452215,"id":"Q5452215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fee4d4f7f8ee7db7d331d62de171def8745d1ea0","datavalue":{"value":{"amount":"+0.8067936","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":"Q2761044$0B08D471-D9F1-4936-8091-FDAF662FC0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bfb61ddf67cf2f033e2a8d21342fa05e8497e40","datavalue":{"value":{"entity-type":"item","numeric-id":2327085,"id":"Q2327085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a9e6e266ae870b0a8e2a242ee0845fdce850cf","datavalue":{"value":{"amount":"+0.80632615","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":"Q2761044$BA0F8333-1D7C-4D56-811A-A0D3500438A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b46ca2fa09e49f40e2a583b11230026303a0ef8","datavalue":{"value":{"entity-type":"item","numeric-id":5859684,"id":"Q5859684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a9e6e266ae870b0a8e2a242ee0845fdce850cf","datavalue":{"value":{"amount":"+0.80632615","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":"Q2761044$E5AE856E-6FDB-4753-9C3E-AF325A903F63","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a48f3356367bfa10861ef58553a0040e6ef95d21","datavalue":{"value":{"text":"Pushing vertices and orienting edges","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2761044$40933E9D-135B-4C7B-88AC-047F82443EB4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6f7fbf6651880b9d76c5e78437f7f8284b8f74c4","datavalue":{"value":{"entity-type":"item","numeric-id":6550664,"id":"Q6550664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761044$8268948A-D48C-4435-9964-AC104F7C04F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"54c114429a952f5c5e1b2a3bbcfcbb9fed66cac6","datavalue":{"value":"Pushing a vertex \\(v\\) of a digraph \\(G=(V,E)\\) is an edge operation which reverses the orientation of all edges incident with \\(v\\). It is proved that the problems to decide whether vertices of an arbitrary digraph can be pushed so as to produce strongly connected digraphs, semi-connected digraphs, acyclic digraphs or Hamiltonian digraphs are all NP-complete. It is also shown that almost any tournament can be transformed into a strongly connected digraph using the push operation and that a broad class of digraphs which include outerplanar digraphs can be transformed into directed acyclic graphs using the push operation. Necessary conditions for transforming a digraph using the push operation into one having a directed Hamiltonian cycle are also discussed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2761044$2BBAD956-8214-4D22-B4F6-B16A5E3ABC68","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"55e284968cff24f9e3e328c51dd86858b1ce4256","datavalue":{"value":{"entity-type":"item","numeric-id":186109,"id":"Q186109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2761044$C7E811EC-61BB-4B2B-B009-096DF5A9847F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2761044","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2761044"}}}}}