{"entities":{"Q631789":{"pageid":633637,"ns":120,"title":"Item:Q631789","lastrevid":63112254,"modified":"2026-04-11T10:40:08Z","type":"item","id":"Q631789","labels":{"en":{"language":"en","value":"Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5865606"}},"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":"Q631789$235774F2-14FF-4120-99D9-2FD5BE24CD25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3d726f4106d7f23e145d6494745620f1f73bf835","datavalue":{"value":{"text":"Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q631789$7432724C-59C9-40ED-8D66-CA04DB37B2A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"637cd972681f335e67ba4aa4ce218bcd29bafa98","datavalue":{"value":"1211.68287","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$522F3EAB-0D5A-42AB-BE6E-07473C367D75","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cfe6566239923ad221fbf52eb228fbed31c46e0d","datavalue":{"value":{"entity-type":"item","numeric-id":266929,"id":"Q266929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$340A325F-14BF-45D2-BCCE-55461EF20385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ce90c2680e016f4f266b0c23fa7c1148b749c7c","datavalue":{"value":{"entity-type":"item","numeric-id":266930,"id":"Q266930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$6571819E-2546-468E-96D2-C8169EB04D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d176ad615a4e6a7168d3f60eb001c162327a80ae","datavalue":{"value":{"entity-type":"item","numeric-id":175510,"id":"Q175510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$D7143972-A202-4480-AC59-E94937A1EDF3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$6BC05722-1238-405A-A4A6-A1608CAD6418","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4f05c15c599566c03aa1303bff626bf49bc05676","datavalue":{"value":{"time":"+2011-03-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":"Q631789$D6B28531-2152-444E-B65A-9ECF17F178B1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$3AFE8816-DD90-47B9-85B7-B961486107CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$557CC7BD-E563-43D8-9BAD-641EDD79F7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$2266C175-FED9-49DB-9406-2698D1522218","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"078c551f353711e093ee5ac5a7cd370bf88ab3c9","datavalue":{"value":"5865606","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$34ED6BD6-2406-475B-8F1A-A13FEBF6B45C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$3C69784D-F4F7-4B2C-9B42-9351DBE03866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d625865ee5e7003796c468a26e87723f176c6f37","datavalue":{"value":"embedding into a path","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$DB66AF41-9867-4CE5-98B1-83B61C25C504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd195618975a5773a609e7679d204d0191e5de0e","datavalue":{"value":"distortion","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$1C3B52D0-AA11-4C51-A131-6BAE46BA9D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$E9B94AB3-C759-4414-9C13-BBC0FCA118DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5c1c72cdf7ac7cc7f979d178ef43b2671c226ca","datavalue":{"value":"forbidden induced subgraphs characterisation","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$91330282-FA61-4B9D-8921-D5F207DC19D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d752149583d7ee9659fd619df8f643680fb8b09","datavalue":{"value":"bipartite permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$AA7CECF9-45B7-4178-BDD2-0D314306D1C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89c7b74075c02a9f90535ca1118f6218f248cc31","datavalue":{"value":"threshold graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q631789$44DC1AEE-C110-484B-A95B-7AFFDB5A5113","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":"Q631789$C9EC19E2-7DEE-4166-A2CF-B7699CD448A7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d17603d06572ab51878e38d88b7a79b1f107ed2b","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.01.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q631789$65DE161F-1076-40C7-A208-530441896EC1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"39ae5ccba662bd9a55b24f068e1425615ef51936","datavalue":{"value":"W2033622225","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$522A11BB-921A-4DD7-B7E7-B5F2F247719E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4921e7812423fe950665854740b5980ad5464859","datavalue":{"value":{"entity-type":"item","numeric-id":3581393,"id":"Q3581393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$C8BC171D-EAA6-4F0E-9FD4-2270660DFDB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0e48837de710bafbce2e289f7fe23c6982404b6","datavalue":{"value":{"entity-type":"item","numeric-id":2921660,"id":"Q2921660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$8054475D-BC05-4DF2-B463-71A6C441C476","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cd422e53967d33fc5108064fa84e115054c52e0","datavalue":{"value":{"entity-type":"item","numeric-id":2934633,"id":"Q2934633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$CC21B8C7-33A5-4064-92B4-3565A83D63F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$F01B5577-ACB3-40C2-A30A-68A5ECA2A401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85746088bc293216b1661a99df67ae49790eefa7","datavalue":{"value":{"entity-type":"item","numeric-id":3638056,"id":"Q3638056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$83591457-9420-4CA5-95E5-6AD0B12A4949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44d98276bed106b5c8656a2241fcaaed29455cbe","datavalue":{"value":{"entity-type":"item","numeric-id":1611292,"id":"Q1611292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$00019F51-1895-4CCD-99FF-397B20E9BDFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b07b5dcf0b43c9f49e2d29db88bee73b1cb11be","datavalue":{"value":{"entity-type":"item","numeric-id":1886097,"id":"Q1886097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$53EF63BC-7E8F-4822-9539-2EFFB865E145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05b4c44b5b82897f5b5bc558ae528113217190c1","datavalue":{"value":{"entity-type":"item","numeric-id":1044045,"id":"Q1044045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$ACFC2E75-844D-43A2-92CE-7F00E1168567","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf895833c738ffb67737531b830e201fa40fed2e","datavalue":{"value":{"entity-type":"item","numeric-id":991793,"id":"Q991793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$7FE97570-6A78-4DB2-B512-2F9AF8F48EB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89faa33019fc04a51e4a6b68236528b2df13c3ff","datavalue":{"value":{"entity-type":"item","numeric-id":3580974,"id":"Q3580974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$9626AEAB-B384-4092-A1B9-4F491B9F6605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5970d68c1e752b9c9b8f5c29659be82f3c6942fa","datavalue":{"value":{"entity-type":"item","numeric-id":3483315,"id":"Q3483315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$BB4A45A9-53FE-4F57-B4FA-C8808CD16CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e786baa016e3559ab71e68a8c9b0f02660fa89e4","datavalue":{"value":{"entity-type":"item","numeric-id":2365550,"id":"Q2365550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$BC5CA373-D974-47BC-AD06-C0A283131CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d1d5524b91a030cb506c147be19b598758c8009","datavalue":{"value":{"entity-type":"item","numeric-id":1899209,"id":"Q1899209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$89637E3E-6AB0-4132-9F0F-DC7294CB2F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c26c1f219206a588a37699fbc3b825c5a7c6afad","datavalue":{"value":{"entity-type":"item","numeric-id":3026359,"id":"Q3026359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$87FB8856-811A-432A-BA10-732220DC2BD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec149a5a7eec323669b1fe3f50faef3f835f63d2","datavalue":{"value":{"entity-type":"item","numeric-id":2921659,"id":"Q2921659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$ED729537-7457-4F23-BAD2-F5FFEB0784A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd444ac2099fb3b5a15da02a0171b8b4a45b7ea","datavalue":{"value":{"entity-type":"item","numeric-id":5588432,"id":"Q5588432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$E5C3B776-4901-48AF-9DBC-D594D94E3247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da2d95ac31a70052a778a9e28ab2a7a081f20922","datavalue":{"value":{"entity-type":"item","numeric-id":1092931,"id":"Q1092931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$5A1089D5-A954-40D5-9C1D-382968347C4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8df6010560b7ca77115a914de6fd65842df1e49","datavalue":{"value":{"entity-type":"item","numeric-id":4296515,"id":"Q4296515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q631789$7F3DC1AC-A9F7-4476-B9E5-6D7665FF0F4D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b5c3f406a1dbbd204d703fc31de23a56e8b6c15","datavalue":{"value":"10.1016/J.TCS.2011.01.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q631789$EC745F10-08BE-4B3E-B726-6E86E88771D7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18fe9712ccd8a7320e453f9047371d16e6589fc4","datavalue":{"value":{"entity-type":"item","numeric-id":3512470,"id":"Q3512470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"444fe95a093aa3d8dd35afc23f14de328e94ef99","datavalue":{"value":{"amount":"+0.9911503791809082","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":"Q631789$D2B0A223-E930-43F0-9F2F-10765F7E53D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c19756128a8fd36166863844b948556e2297be50","datavalue":{"value":{"entity-type":"item","numeric-id":991793,"id":"Q991793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"caa3cdf243b5a00bedacca8454e5c9c32fcedf30","datavalue":{"value":{"amount":"+0.8688755035400391","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":"Q631789$FF21E3F8-7941-4E3C-BA4D-53B6C816BE22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ad62a2f9b82ef72fbc162c4b84f0abb935b1ba6","datavalue":{"value":{"entity-type":"item","numeric-id":5851098,"id":"Q5851098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5941ddb657a36bed8e5879df1b1d805a51cb626","datavalue":{"value":{"amount":"+0.8327695727348328","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":"Q631789$5F4A6650-4B7B-4D0F-9656-4ADF61605AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32d5188ac3f2c0dfab0ba6c409e00e0b37005029","datavalue":{"value":{"entity-type":"item","numeric-id":5115789,"id":"Q5115789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"908c87351807e824d668d02464bc0f1fa495a43b","datavalue":{"value":{"amount":"+0.830206573009491","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":"Q631789$D4E106D5-F51C-4516-B631-6A0834598A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd0448bba2fac3814bfd955fcecf2622812da68a","datavalue":{"value":{"entity-type":"item","numeric-id":551173,"id":"Q551173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"092491e96826a7b07e575d15639674c1a53127bb","datavalue":{"value":{"amount":"+0.8288303017616272","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":"Q631789$BE24126E-45E7-4EB7-85C6-86C5F2F5370E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_minimum_distortion_embeddings_into_a_path_for_bipartite_permutation_graphs_and_threshold_graphs"}}}}}