{"entities":{"Q2563512":{"pageid":2574255,"ns":120,"title":"Item:Q2563512","lastrevid":78896390,"modified":"2026-05-06T12:41:19Z","type":"item","id":"Q2563512","labels":{"en":{"language":"en","value":"Path problems in skew-symmetric graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 958132"}},"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":"Q2563512$0837008C-C98E-4ED6-BE0E-88379F62D14E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"736de69603461a6c52f062d001be28c08108dd53","datavalue":{"value":{"text":"Path problems in skew-symmetric graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2563512$E2DCD28D-C55A-410A-95D8-E37BAFF2AFF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a9ae6aaa5f746de11af4dc2f69fc245e4811d0c4","datavalue":{"value":"0867.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563512$92D54978-421B-488C-A6C1-8688FED99223","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9322ffa036f45e0a5b2b864297353ed321a917bf","datavalue":{"value":"10.1007/BF01261321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563512$E46FD9A4-C855-444C-8F75-D396145FE78F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"292ee0ed60d229834f4ba04d9e68598fca7e73c5","datavalue":{"value":{"entity-type":"item","numeric-id":536068,"id":"Q536068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$A8B7E996-B994-4474-8961-880C6BBC78B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"14fc360ec3034cf7b4974dd2757eb533d1dfaac7","datavalue":{"value":{"entity-type":"item","numeric-id":423889,"id":"Q423889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$01796471-2216-4EF4-9145-6BAD79339405","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$EEF1E274-AE3C-44AD-A161-02DC20EA9B30","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b34f93578f34bf813eb265da2a0d58fb3d8dd5ea","datavalue":{"value":{"time":"+1997-08-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2563512$1AC7B57F-9DF6-4AA1-A6D2-D7118C8B80A9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f394ecbce8f11e38ef3bf6bd22635237b861fcfd","datavalue":{"value":"This paper concerns path problems in skew-symmetric graphs. A skew-symmetric graph is a digraph \\(G=(V,E)\\) together with a mapping \\(\\sigma\\) of \\(V\\cup E\\) onto itself such that (i) \\(\\sigma\\) is an involution \\((\\sigma(x)\\neq x\\) and \\(\\sigma(\\sigma(x))=x)\\); (ii) \\(\\sigma(v)\\in V\\) for every \\(v\\in V\\); (iii) \\(\\sigma(e)=(\\sigma(v),\\sigma(u))\\) for every \\(e=(u,v)\\in E\\). Generalizations of the standard graph reachability and shortest path problems are studied. The authors establish combinatorial solvability criteria and duality relations for skew-symmetric path problems and use these to design efficient algorithms for these problems. The algorithms are competitive with the fastest algorithms for the standard problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$AAA7D8CE-885F-4477-A535-8AAECE7D7A5D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563512$2643DB1E-1432-410D-9BF4-5050FED72D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563512$7327824A-63E1-4FC1-AC10-7EFB22A961F9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf7f1b4d881d6b32b0ffd62786ae56f31d0931c5","datavalue":{"value":"958132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563512$5A21979C-A344-4D0E-8EC7-41D541CED64E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9f089402631383241fc28cbdb01ed76950390dca","datavalue":{"value":"skew-symmetric graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$758AA815-6492-4A24-BC5C-62132EA89E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$400DBC6F-6673-4735-8C72-6CE127DF46B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aff5d89279bcdc72990d01d565b9d60000fd4d1b","datavalue":{"value":"graph reachability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$5BA576E1-0C33-4718-87C1-26B7763708C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b4835c057206e9597aecfe39ef265eb239c88a1","datavalue":{"value":"shorgest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$BA6B0BA7-86A5-433B-A713-B9F8E24708CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d1ecf978a28e5d1baefdbd10dbc4f102a6158a13","datavalue":{"value":"duality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$06602D14-0CE2-4CC4-8B2C-E04BC6D771CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c444ecc79f81560504ba94a0295898295318e56","datavalue":{"value":"path problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$9C7F1530-3EC3-43EC-9909-FB73E415C9AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff9f78089affef06c072081bb824e40f99a75bd9","datavalue":{"value":"efficient algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2563512$8967E620-5611-484B-BB4E-27F926D79782","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eee744981d92ac19b8d353f3a45a83ebd916fb73","datavalue":{"value":{"entity-type":"item","numeric-id":558237,"id":"Q558237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$8D93C937-097B-4EA4-A96A-73807E986AE2","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":"Q2563512$0BC2E70D-5D24-4929-9C18-C87F303409B5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"061885fa573451da1302a78a271f913f69225f7d","datavalue":{"value":{"entity-type":"item","numeric-id":3249327,"id":"Q3249327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$C65F92ED-1461-4948-8197-818D0DB6595C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f61c5d68d33f8ea7723f3ac70afbbc88052e3402","datavalue":{"value":{"entity-type":"item","numeric-id":3258697,"id":"Q3258697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$376906CD-2D71-4C67-9040-7F82B6116BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$D0E96F4E-B21F-4688-AE7D-8BC42F1CD13B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$C2733737-E7F0-4447-95E9-887222666488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$715737DD-B54E-480F-BF6A-41F921C65B39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$68465C0F-CA24-4DAD-B6B8-6F6C6E3CE7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"271059027ec9c0e0491187496cb25dd92d2df81b","datavalue":{"value":{"entity-type":"item","numeric-id":5675543,"id":"Q5675543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$5A824608-4886-45B1-A351-E25D7376F662","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3544ff5c3325f5ac1e5dcd2fd92020bf1b6189fb","datavalue":{"value":{"entity-type":"item","numeric-id":3292914,"id":"Q3292914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$0CDB4729-6C20-439C-BCE8-26D164F4CD1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17b46f23e1d95210ec444c78dd7a8edd18f2e48d","datavalue":{"value":{"entity-type":"item","numeric-id":1062461,"id":"Q1062461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$FD6E6306-AEE9-4F20-8BC3-8FD666FC3A13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d22d58e11ccbeb91d3df03036c0ddbe092bba79","datavalue":{"value":{"entity-type":"item","numeric-id":3140424,"id":"Q3140424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$E4611BCB-D7F7-4A53-978B-85178A0C9B89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e82bcb2778a4852c1efd5e7b86af961a9bc9da53","datavalue":{"value":{"entity-type":"item","numeric-id":1337137,"id":"Q1337137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$2D9AB5DF-4C99-41DF-A49A-66D6A101B810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9a3ada332d9b1d8bf5360191802e9e5d56978f0","datavalue":{"value":{"entity-type":"item","numeric-id":5659592,"id":"Q5659592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$A5364E2F-F809-4A42-90A2-A70770F1D682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$7FE9AC49-832D-4500-AA7B-73C612D8FD99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfba955c32dc153431f5c99ab1d6a49daa930c11","datavalue":{"value":{"entity-type":"item","numeric-id":5785127,"id":"Q5785127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$8FCC386B-62C7-4DC8-A0D4-F8212CC39F25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ca850c5805b8b95773e5e7121960df5aa76b4b5","datavalue":{"value":{"entity-type":"item","numeric-id":5543330,"id":"Q5543330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$475D499F-CFA0-4136-AA13-AC8D35A3494E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3585bbaf4103bad430323a4d8ec5d8173799a2b8","datavalue":{"value":{"entity-type":"item","numeric-id":678872,"id":"Q678872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2563512$4EBADE84-4493-4DE6-879C-C0B74BF28F2F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a592284e69433ad5f5aca8d47b14a35656ca1cd","datavalue":{"value":"https://doi.org/10.1007/bf01261321","type":"string"},"datatype":"url"},"type":"statement","id":"Q2563512$7809AC00-F2EA-4403-AC3E-D283B62141B0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"98cb5b13bbb7e684da750ff0bf5ce73e5133fdcc","datavalue":{"value":"W3136397722","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2563512$D91E4369-44CB-454A-921D-97BA18C1467F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a307dedf09a152ba9dd71eb1002153eb11bbdd9","datavalue":{"value":{"entity-type":"item","numeric-id":3128915,"id":"Q3128915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2919955f9126c01eaae2dab1fcae1eb10ab6ea66","datavalue":{"value":{"amount":"+0.9448050856590272","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":"Q2563512$478A67EA-8D56-49E8-8463-47C1676EE51B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85517ca965edf6fc25bd60814386527b1675fa9a","datavalue":{"value":{"entity-type":"item","numeric-id":1013299,"id":"Q1013299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c95cd3b1bdf56d3ecdcba054d6acc52c4464393","datavalue":{"value":{"amount":"+0.7601235508918762","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":"Q2563512$BC4DF538-6F8A-40A8-9422-DFFBBFFD9C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a2fd6f3c162a0e5b1e7d7bac3d5baaf3d084c83","datavalue":{"value":{"entity-type":"item","numeric-id":6102298,"id":"Q6102298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25b876e3a0369dc0604ec8e48ee488af7615636c","datavalue":{"value":{"amount":"+0.7445178627967834","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":"Q2563512$E574D3CB-E5AC-4B6A-9C49-A2F4E06EAE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ca571d8a37c5e43e38afec09e3a3a1461e62b05","datavalue":{"value":{"entity-type":"item","numeric-id":678872,"id":"Q678872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d80049b0945d1f14a2d86bb314e45a6f3e1a278","datavalue":{"value":{"amount":"+0.7267780303955078","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":"Q2563512$5F80362A-5DC6-4012-BD3E-A6DB8722A61F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Path problems in skew-symmetric graphs","badges":[]}}}}}