{"entities":{"Q1123899":{"pageid":1134648,"ns":120,"title":"Item:Q1123899","lastrevid":49298788,"modified":"2026-01-06T22:28:39Z","type":"item","id":"Q1123899","labels":{"en":{"language":"en","value":"On orientations and shortest paths"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4110720"}},"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":"Q1123899$A262BFE1-A945-4687-B5BC-BC305D412AF3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"acc80774ad015d26dba5d72d7f1d2d8be1c590ab","datavalue":{"value":{"text":"On orientations and shortest paths","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1123899$CCA15BA6-9F02-4A9F-B4C4-11CF0005B355","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"13c19e625be02535ad758bd1975a6e4d3617f68d","datavalue":{"value":"0678.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$A0283AD7-9B05-4838-BD49-C1393BCD96D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7f81f46dc08dd60009b3097ee873092ced6e14d1","datavalue":{"value":"10.1016/0024-3795(89)90481-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$5E8BA6A8-3951-4F23-9BEB-633CB7F0E027","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f54f6d518946c4faa452b02158d231b7ca863f0c","datavalue":{"value":{"entity-type":"item","numeric-id":233539,"id":"Q233539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$1C132064-61DE-4221-BD64-288B5BD2B325","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"be690050f94666bf6766a43de05350885a6401a1","datavalue":{"value":{"entity-type":"item","numeric-id":613423,"id":"Q613423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$416D5C31-8E13-495F-958D-D8D6219109A9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$F92FED64-CEFA-48D1-AA35-F7D080AC4877","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1123899$84F48D77-811E-4268-B627-DCBD2EB4918A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"544f08decf094de571266554c68f758c409c33a0","datavalue":{"value":"A digraph \\(G'\\) is called an orientation of a graph G if \\(G'\\) is obtained from G by assigning directions to its edges. For a given graph G and m pairs of vertices \\((s_ i,t_ i)\\) \\((i=1,2,...,m)\\), an orientation \\(G'\\) of G is called feasible if for every i \\((i=1,2,...,m)\\) there is an \\(s_ i-t_ i\\) path in \\(G'\\). In this case the set of pairs \\((s_ i,t_ i)\\) are said to be feasible. It is shown that for a given connected graph G and two pairs of vertices \\((i,i')\\), \\((j,j')\\) a feasible orientation \\(G'\\) of G exists if and only if for every partition of the vertex set of G into two disjoint sets \\(V_ 1\\), \\(V_ 2\\), such that \\(i,j'\\in V_ 1\\) and \\(i',j\\in V_ 2\\), there exist at least two edges of G that join vertices of \\(V_ 1\\) with vertices of \\(V_ 2\\). An orientation \\(G'\\) of a connected graph G is called ideal with respect to a given set of pairs of vertices if it does not increase the distances between the members of any of the pairs. The authors describe an efficient algorithm that determines whether an ideal orientation with respect to two given pairs of vertices (and any positive edge-lengths) exists, and if so, it provides an ideal orientation with respect to these pairs of vertices. It is also shown that the problem of recognizing whether or not a given connected graph has an ideal orientation with respect to two given pairs of vertices can be solved in polylogarithmic time on a polynomial number of processors, i.e., the problem is in NC. The problem of determining whether or not a given connected graph G has an ideal orientation with respect to an arbitrary set of pairs of vertices in a graph is shown to be NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123899$EAD851A4-D759-4F6D-9248-E98A0999DC1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$3A9648DA-618F-435B-B537-4F6283E29513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$7F6A63A9-5F95-4753-937D-057475AB28D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$215917B1-1FDE-4AAF-8913-03E827026E30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea3b9d45d87914dd417bffdfe63c0bac66e902ae","datavalue":{"value":"4110720","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$83772A77-B6CB-40E9-91E2-A0D2E393B2C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85eef5242ed0d57acc9caf7d48d82888e646d12f","datavalue":{"value":"digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123899$03BF04B3-A943-4981-AEEE-FFB1AFFE8EFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9624a48a2085c44911fe999911560e0333cc68","datavalue":{"value":"ideal orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123899$E84BD4E2-21E6-4669-95BF-663812F4B549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b35636aeae7c064244b5bc59612ab87513a2223a","datavalue":{"value":"polylogarithmic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123899$4EEE2456-70B2-4550-B7B1-CEAE794F4E47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1123899$A6465276-7802-4989-AF7D-3BD2CC029C68","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$EE55B760-07AA-45D7-A0EE-BA432EBA6176","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":"Q1123899$D1623BBF-687B-490F-8AD4-283D0FF93E62","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6b1dcd1beb0e4e1648e8639847a0393b402d4f33","datavalue":{"value":"https://doi.org/10.1016/0024-3795(89)90481-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1123899$48D8B504-296E-4445-91F0-E189B7BA469D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"59f232105487872ac82c9d7c396e0f368e0fdedb","datavalue":{"value":"W2125585605","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1123899$AB98114A-8570-4C41-AF1B-37A7DCC36021","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a52875b0698817b758136e6eeaf14258b7242a4","datavalue":{"value":{"entity-type":"item","numeric-id":3900089,"id":"Q3900089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$1A9E25AF-F40F-4CE7-9DC1-4573C982C85E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4466e412628c87e0f897dd7fe15ffcda3043ccb","datavalue":{"value":{"entity-type":"item","numeric-id":1219300,"id":"Q1219300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$CBDF41E4-BD67-4D5A-94A6-C065B786FEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55223ae6f91a9a3c0f6a3be0cfb6236eaf5fcb6a","datavalue":{"value":{"entity-type":"item","numeric-id":4132234,"id":"Q4132234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$3DDF5889-C3EC-4FAC-A19A-F9C45DF9E896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c2045a7ec56e01f15e3eae4db248ef2b73a81db","datavalue":{"value":{"entity-type":"item","numeric-id":1132111,"id":"Q1132111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$57D91F0D-7468-44C0-81D0-3A4E06BE66D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a4f1cb6ec9ad874b28603d7ef07271b5d1f94f7","datavalue":{"value":{"entity-type":"item","numeric-id":1144041,"id":"Q1144041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$17EBC8C7-74AE-445B-B014-07F693371B97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6b1dc0d2e548f9cda9832ad27d3c5a8b4dcdc9f","datavalue":{"value":{"entity-type":"item","numeric-id":4739952,"id":"Q4739952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$629E27D1-8FF8-4E35-8FE8-70932FE0757D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a14e94c8d91f804daff7f3d4a6efdc8448e27a7","datavalue":{"value":{"entity-type":"item","numeric-id":4170745,"id":"Q4170745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$AFB2D1FB-B097-438C-A916-F6163F4C3D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e0b5ed8028c5ab53b238424e6b9110abc13056b","datavalue":{"value":{"entity-type":"item","numeric-id":3220093,"id":"Q3220093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$73936A36-2EAB-443E-8878-D8BC945AEBA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$5BE321A7-26CD-423A-82C6-A8C16D4D70FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$42FF424D-994A-48DB-AA62-27E974781EF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c439d80aa48b2235589f2742abd16fc8d19d0fd","datavalue":{"value":{"entity-type":"item","numeric-id":2532282,"id":"Q2532282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$9F370AFA-7C84-459E-8F36-69E352607D6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ce6021c10f5d1308684258114e5c8905ea1a39e","datavalue":{"value":{"entity-type":"item","numeric-id":3716851,"id":"Q3716851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$24A3E0F1-E402-49D6-AD72-A9A9F2E12A7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"630a865d8f4ac3696793e9f973ec3305d4306b75","datavalue":{"value":{"entity-type":"item","numeric-id":5611649,"id":"Q5611649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$239475AD-BD2C-4DA8-B93C-28B801454FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$E55E154A-A4DE-43BB-B6C2-D0CC62635665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aecbfbe764c73b405203223e4c4ac2dee201dd0b","datavalue":{"value":{"entity-type":"item","numeric-id":3338254,"id":"Q3338254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$1CE179FC-FF17-4E32-9664-80B6CA3FF2F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5f5448c92b03afe0ee9b9ec7d7ae88a567b335","datavalue":{"value":{"entity-type":"item","numeric-id":5774643,"id":"Q5774643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$B942E356-87DE-4DBF-A207-28CF8E25C363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d835ccc7da104c96eb1a22d7d8e47a280dbf09","datavalue":{"value":{"entity-type":"item","numeric-id":1150632,"id":"Q1150632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$98BEE032-F670-46CC-8585-F9762CD69DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32cfb1bd9a2e4985fe859e378e81598a196911d8","datavalue":{"value":{"entity-type":"item","numeric-id":3930654,"id":"Q3930654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$AE6B5DFA-4426-471F-9C14-D50ED38572CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fb93bc202fb8748c4ae6023a86a3a42cab16977","datavalue":{"value":{"entity-type":"item","numeric-id":3828023,"id":"Q3828023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$3BAFE6F7-4BA7-41BE-A900-51FB279C00E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$B7E5DB54-4C23-40C9-B18D-5D13F1F136DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f37749221f764100ba8ead8ef66d9f89873d16da","datavalue":{"value":{"entity-type":"item","numeric-id":1844076,"id":"Q1844076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1123899$AA8DF361-978E-472B-B593-8112CE38586A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acfe3587495dcaf8ffae86b603bfa94bb199e381","datavalue":{"value":{"entity-type":"item","numeric-id":3652228,"id":"Q3652228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0da1933555750433a524b9eef5df30e7c420e1e","datavalue":{"value":{"amount":"+0.7933002710342407","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":"Q1123899$13AFD5BB-9C81-4C8B-8DAE-26C79C1F5403","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96ba52eef9b62b6826a7a396d6fbc0defeb4fee0","datavalue":{"value":{"entity-type":"item","numeric-id":1939659,"id":"Q1939659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82b918f45d9a053a5a4606ca47ffd5d934aca53d","datavalue":{"value":{"amount":"+0.7897172570228577","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":"Q1123899$4ABDAE15-8D7E-4D21-8DD4-DD2F83CDA393","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c41e7ad49c53ddf8bbee6fc93ca1a2e44a015207","datavalue":{"value":{"entity-type":"item","numeric-id":1057281,"id":"Q1057281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e027cb268bc628eba3d28c8344363e13b4de5bd2","datavalue":{"value":{"amount":"+0.7849922776222229","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":"Q1123899$17D81287-FB15-4FDC-A3BD-D87971E04E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"373b08e3fa91f2146866147f0bdb1e3c9b8c0be5","datavalue":{"value":{"entity-type":"item","numeric-id":290248,"id":"Q290248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"000285e6124601efa1a2f9462fa898c73a7af187","datavalue":{"value":{"amount":"+0.7849592566490173","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":"Q1123899$2F0B6ABC-2555-4CDB-B973-FF5CD4FD939F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7b67cfdaaa50fba24e987f22f628cc2c49d9a09","datavalue":{"value":{"entity-type":"item","numeric-id":412352,"id":"Q412352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f60b1ff6beff7772d1394ca610f043939ebf8fd0","datavalue":{"value":{"amount":"+0.7790966033935547","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":"Q1123899$EBD51CF6-8CB8-445A-9AD0-2D37CD101DEB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1123899","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1123899"}}}}}