{"entities":{"Q686277":{"pageid":688126,"ns":120,"title":"Item:Q686277","lastrevid":42643400,"modified":"2025-07-07T15:23:38Z","type":"item","id":"Q686277","labels":{"en":{"language":"en","value":"Computing equivalence classes among the edges of a graph with applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428122"}},"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":"Q686277$86683C08-6B2D-4BF9-A41B-5B4701330ABC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f011f4b247dc9dda17ed5a5dab81e6499a6a10f","datavalue":{"value":{"text":"Computing equivalence classes among the edges of a graph with applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686277$C2BEAC4C-C3B1-4759-996C-FB9AAA8F14C8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b628acfaf4a139972f6f08f1fdf0ee023184367f","datavalue":{"value":"0795.05130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686277$E5E72DD2-C4B7-4777-81CC-33C77BBD02FC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2fff035e583babfc5f1424dd46f72e4f7c376a87","datavalue":{"value":"10.1016/0012-365X(92)90274-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686277$ACBEE398-32FD-476F-A89C-26E288260970","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"69dce50474062592c3f0f665321210ea0d53ae77","datavalue":{"value":{"entity-type":"item","numeric-id":170469,"id":"Q170469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$20473612-F294-40E1-B87C-BB113EA2FEAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b09f0ce0920eca24512e9f5bc31e5cc4957d4533","datavalue":{"value":{"entity-type":"item","numeric-id":686276,"id":"Q686276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$98DE8FA7-050D-4DE5-B69C-A36F5E5F99A2","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":"Q686277$33A263CE-4788-4817-9C26-2BECB050A378","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"75a8b7e8c6887771540dbf878c1b8ed98975502d","datavalue":{"value":{"time":"+1993-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686277$2D710A06-5876-49FB-9CF3-F09F48C756F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a8f4ee5c93d21eb05bfe2dfb98b6a089ef0aec44","datavalue":{"value":"Let \\(G=(V,E)\\) be an undirected graph. We denote by \\(d(x,y)\\) the length of a shortest path in \\(G\\) between \\(x\\) and \\(y\\). Define a relation \\(\\Theta\\) on \\(E \\times E\\) as follows: for two edges \\(e=xy\\) and \\(e'=x'y'\\) we let \\(e\\Theta e' \\text{ if and only if } d(x,x') + d(y,y') \\neq d(x,y')+d(x',y).\\) This relation was introduced by Graham and Winkler [\\textit{R. L. Graham} and \\textit{P. M. Winkler}, On isometric embeddings of graphs, Trans. Am. Math. Soc. 288, 527-536 (1985; Zbl 0576.05017)]. It is easy to check that \\(\\Theta\\) is reflexive and symmetric, but not in general transitive. Hence the transitive closure \\(\\widehat \\Theta\\) is an equivalence relation. This paper is concerned with finding the equivalence classes of \\(E\\) with respect to \\(\\widehat \\Theta\\). A method is described which allows to find these in time \\(O (| V | | E |)\\) using \\(O (| V |^ 2)\\) space. This should be compared to the obvious algorithm with complexity \\(O (| E |^ 2)\\) with \\(O (| V |^ 2)\\) space. The authors remark that Feder [\\textit{T. Feder}, Product graph representations, J. Graph Theory 16, No. 5, 467-488 (1992; Zbl 0766.05092)] has improved the space requirement to \\(O (| E |)\\). Computing these equivalence classes is a first step in several graph algorithms. As examples the authors mention isometric embeddability in hypercubes and factoring a Cartesian product.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686277$C142B0D1-B29D-484C-A5A7-20DA94769668","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686277$FE3BB8A4-661D-48FA-B8A8-CC0C5480DA65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686277$C15FCD2A-71F0-4F2B-817D-9CACF2033C4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1225fcc322f7855972a6234e4cc25f8b5d8cff6","datavalue":{"value":"428122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686277$CD9ABC76-55FB-4F8C-ABEF-0FFF885E7430","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f1413856faefc21fbe403cafe86436fc7cc4906","datavalue":{"value":"equivalence classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q686277$4CEC5F61-67B9-4B84-8280-F782C658E161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q686277$0A33194E-7317-46A3-A840-98CEBB07A428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28a8d05e47492d5ec416f259b2de1f51fdac9796","datavalue":{"value":"isometric embeddability","type":"string"},"datatype":"string"},"type":"statement","id":"Q686277$DB8C8185-7C54-4E7D-9966-2009B1E39079","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":"Q686277$A51C5F2B-6354-4411-B905-A6D4B7D323F4","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":"Q686277$3DAF50E0-03B2-4733-AFCD-27AC08AC76C3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"916c78bd8a9f067b63156f367131d2b8139a669f","datavalue":{"value":{"entity-type":"item","numeric-id":4028106,"id":"Q4028106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$67E8AB7D-C345-440D-A3C7-7ECB11EB7DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2436afecea717d449f669935f2d48c064b2aa71","datavalue":{"value":{"entity-type":"item","numeric-id":2555084,"id":"Q2555084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$CC5C535E-18E4-438D-BBD4-1577D13583DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f5623ce033ee16b98147a29e4b5dcb1e8682fa0","datavalue":{"value":{"entity-type":"item","numeric-id":4020705,"id":"Q4020705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$94BD5B78-403C-45A1-A31C-4F395C829264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5e21a0d2f846c7b5db53c68e1a2923e4c158d6a","datavalue":{"value":{"entity-type":"item","numeric-id":1067411,"id":"Q1067411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$54AC5EC1-5C12-439A-8C76-E071898545E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c25249474734f117fbdf2b2d4cabcd088103c2e","datavalue":{"value":{"entity-type":"item","numeric-id":686286,"id":"Q686286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$290DA7A3-5270-4852-96CE-1B25C85BE9CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67f29bec88daf336d76f38f176d5988388118c07","datavalue":{"value":{"entity-type":"item","numeric-id":3697031,"id":"Q3697031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$CA9717BE-44BE-4401-8DA3-E68E36CBA481","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98a13f1fc7727af9443b256ff0c9b5991ce3ca9e","datavalue":{"value":{"entity-type":"item","numeric-id":686292,"id":"Q686292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$AFDE04DB-4A77-4D4F-BA46-058DD1613280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$B1AE9795-EEF7-4204-8B9B-ADA5467E37CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"844a42744531315d091ae549af20101536f6e872","datavalue":{"value":{"entity-type":"item","numeric-id":772606,"id":"Q772606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$79B82240-55C1-44CC-BF3F-7652AEEA837B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88397f07dd795af1c91d1deee0e50c9f89cd50c1","datavalue":{"value":{"entity-type":"item","numeric-id":787171,"id":"Q787171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$082A22AF-39FB-4F8A-ADCF-8ABAC75C7A5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30ee28d0ed23e167ceb3fdd62454860bee3279de","datavalue":{"value":{"entity-type":"item","numeric-id":579285,"id":"Q579285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686277$DBCF72E6-1CFC-4006-ADAF-AA4348D6867E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50c51972680242c3b6976a0f26ac682526ca55f1","datavalue":{"value":{"entity-type":"item","numeric-id":4383730,"id":"Q4383730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29d25ba43410c4d94ee1a2224461edc95bce2a09","datavalue":{"value":{"amount":"+0.75494057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$895785AE-38E7-4DDD-96EE-C8DB8AF22C91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c90fddc85bdde81e6b51e6e52aeeb2c0614f976b","datavalue":{"value":{"entity-type":"item","numeric-id":2819594,"id":"Q2819594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec282622a83ae7b08d002678d6e5c0860f050a47","datavalue":{"value":{"amount":"+0.7361276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$E0B8DFCD-CEB5-40E8-92D5-CBF119C2D3E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33a236dfaf6e06b46fa3f1b7a61fc9ad4eea9387","datavalue":{"value":{"entity-type":"item","numeric-id":4362733,"id":"Q4362733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdbc5d18b88293b41740f0da4c66063113c67ac8","datavalue":{"value":{"amount":"+0.73332083","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$DEB5A1AB-F6F4-4FB7-8593-7A7128D29BB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca0ed18c811700e6c6a3df9e2b5771b41c566fd9","datavalue":{"value":{"entity-type":"item","numeric-id":5321080,"id":"Q5321080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6e8ead1e3abfbc1690050a45ab8ea047c85fa10","datavalue":{"value":{"amount":"+0.73064876","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$20371B4F-5B74-44C4-8053-9132371B08EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ffc508fbe6cb95be49524221960a987bbd83455","datavalue":{"value":{"entity-type":"item","numeric-id":4028102,"id":"Q4028102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d74b885f851a8b7aa1247127cfed88cab31e8f4","datavalue":{"value":{"amount":"+0.72641313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$B9418735-862B-49DB-BB47-EBF93E14CC57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c38b7b428b4cd5a0dc9af6474dc8801c20ceb6e8","datavalue":{"value":{"entity-type":"item","numeric-id":3620818,"id":"Q3620818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b3425cf89ea4e8a8c13cd9f2a8a9c6453d1f981","datavalue":{"value":{"amount":"+0.7221383","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$FF80E148-92C7-4D0C-B5FE-42AF31E81246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae5e7a7ff78abaaa26b3f80cc563868d3acf3252","datavalue":{"value":{"entity-type":"item","numeric-id":2872114,"id":"Q2872114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ce9597d2fc9a42e70841d8101894fef61975a76","datavalue":{"value":{"amount":"+0.71904874","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$6239C4CF-6784-4DAF-8944-60FE76AD8516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e9c08f3481635afb85425972eca5d5a5bdc0227","datavalue":{"value":{"entity-type":"item","numeric-id":1067411,"id":"Q1067411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c50f5c09da1953b45718e61252376ed5d397092","datavalue":{"value":{"amount":"+0.71901715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$6E4064D9-4C14-4320-A1D5-DC4985C14E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5f701f0deb314732ee1a1ae07183ffe673ff0ec","datavalue":{"value":{"entity-type":"item","numeric-id":5150526,"id":"Q5150526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90b8efe541d9828c6f42ba1dad90d5d3ef930bc2","datavalue":{"value":{"amount":"+0.71730196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$D4808ECB-D428-4A2A-A04D-11D53FECEDAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc0945f8812e70f8e833c2de5b244d73c3b8334f","datavalue":{"value":{"entity-type":"item","numeric-id":4830992,"id":"Q4830992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea5734b47cb31551b82bce2bf4666dda5990550e","datavalue":{"value":{"amount":"+0.70477945","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q686277$67A529ED-E701-4316-9E3D-87E9CAA3C5F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:686277","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:686277"}}}}}