{"entities":{"Q2515582":{"pageid":2526325,"ns":120,"title":"Item:Q2515582","lastrevid":72751047,"modified":"2026-04-14T07:31:22Z","type":"item","id":"Q2515582","labels":{"en":{"language":"en","value":"Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6470576"}},"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":"Q2515582$2E49EBDB-3597-41C2-AB35-289AA7DFAEE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0f5e3749ac5bbdfd68d52f1cebcb03570e4f3179","datavalue":{"value":{"text":"Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2515582$C847502E-6A84-48A8-8BB4-3D6BF9291250","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2452511f68eca8f37d3a2062123231aa1a023f3a","datavalue":{"value":"1317.05163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$54C694F3-60DD-4BC9-B10E-B31FF415EB6A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfa5736c8854d6c8e71ffee7d0d95f9b7115da16","datavalue":{"value":{"entity-type":"item","numeric-id":243612,"id":"Q243612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$928416DD-3ED6-44D4-B761-29627D41F8C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e2fa2fe09e547e1df6479077394a09016f353e7","datavalue":{"value":{"entity-type":"item","numeric-id":312639,"id":"Q312639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$7C6DBF87-7F1D-4B0A-83E9-F592EEC995FC","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":"Q2515582$E2DA037C-D8C9-4AC6-B29D-21A16049E1E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143a47b7cf174256ac299daaf18bbff0086c7a43","datavalue":{"value":{"time":"+2015-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2515582$41E1CB64-F280-48DA-9423-3695DFCAD85B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$729CC249-3004-48E5-80AD-089145A89351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$A382928F-A91E-442A-90AB-9C8BEE0D3A60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$56A4E0EC-867A-430C-9355-45DEA5FEB1CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7c89a280ec1c1c8a6ba601ebe5c8c9252342ea8","datavalue":{"value":"6470576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$AD951394-1228-438B-B774-F7F1F88462A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7642d8b032ac6ec79fcbf380f24fdc21e9f421e","datavalue":{"value":"Cartesian product","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515582$EADCE11A-B52A-4932-AE8C-83F82DA0BEEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4b98b5353082f5ae3dd3eedbb2c57d8903e4ca5","datavalue":{"value":"directed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515582$36FD7A4B-C44B-46E3-898A-A87D4711C12D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5186fd99999e6921db65766363ee98e6a615dadc","datavalue":{"value":"linear-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515582$90DEA0A2-C222-4AFB-944B-81D9560B45DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91d56a4afd558ef6ff4c6e0fb5abbf85ac225963","datavalue":{"value":"graph decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2515582$FFA2D010-6AB2-47C4-93F4-5758882196D9","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":"Q2515582$784B8332-A1FA-42F3-949D-929608ED78C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e7fccddb541d4ba6f8d62c1b76e5b5e318f2a0b7","datavalue":{"value":"https://doi.org/10.1016/j.disc.2015.06.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q2515582$C702D4E3-72DA-4F1B-9602-3FDA57E5311F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"97fd61dfe97ecd1afcd1129368764d8f9761b1cb","datavalue":{"value":"W1036516582","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$674F8827-5B4D-407B-875E-C487EE382ED9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f268cfcd12ecfd4de0cebd3c52b6a3a1aa4de0b","datavalue":{"value":{"entity-type":"item","numeric-id":1210332,"id":"Q1210332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$23BEBC55-EEE6-45AE-A884-112EFE1D8334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$EACE619F-D78C-4FFD-918A-BD8D676AB8F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c8a363057a4e1076a995fc11f63004f266663b4","datavalue":{"value":{"entity-type":"item","numeric-id":4925263,"id":"Q4925263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$F647E5C8-CE34-483B-8F50-08A5126263D2","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":"Q2515582$2ECBB859-BBAB-44E4-8DE6-FF7235CDD789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"255c900da22e43faee36db7d10bad35f785f1f5e","datavalue":{"value":{"entity-type":"item","numeric-id":1098860,"id":"Q1098860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$5C081DCB-C88F-43C8-B5D5-B8139440EFD7","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":"Q2515582$BA43F05F-6338-4219-9E5A-7B2B713567DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d543e0e002ccb8d633dfbf8d6e835be577ec4d3a","datavalue":{"value":{"entity-type":"item","numeric-id":3005852,"id":"Q3005852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$999F2F3F-BE00-4352-AF9C-9958BD0A19B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f33796fa282fba29440322001214063c4294b8a3","datavalue":{"value":{"entity-type":"item","numeric-id":864136,"id":"Q864136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$6EBCD4C9-80DD-42E2-AA9A-74199D1A06A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f061db89453be7a80fb0b0f51aa03004da1074a","datavalue":{"value":{"entity-type":"item","numeric-id":941431,"id":"Q941431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$E010E592-7FAA-453B-B733-DD6464B186AC","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":"Q2515582$6B6AE166-C74C-4CBB-BC7C-B627C1B52E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f254905ff1ada4c9ba698b1b0da28d301a3fb7","datavalue":{"value":{"entity-type":"item","numeric-id":1396949,"id":"Q1396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$296127F8-DB83-4E93-9270-9E9D838CF29B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d040d73b03d22b97778cbb8e9a75267dc923ec08","datavalue":{"value":{"entity-type":"item","numeric-id":4936660,"id":"Q4936660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$E61ABFF3-A3BE-4BAC-9650-B7902CF0D06F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d05a5de334379278631d3f0c78b0cf6c1f50b94","datavalue":{"value":{"entity-type":"item","numeric-id":1072575,"id":"Q1072575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2515582$F31DFD51-9E9E-4780-BCA5-315133B60A2C","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":"Q2515582$CFAAE67F-5040-4260-9335-E7C1FD80B586","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d0c7b6773259b34f44d37171b88d7beb1b7ba5c1","datavalue":{"value":"10.1016/J.DISC.2015.06.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2515582$EA75F728-195C-4D40-A42B-BDCB07F22FA1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7762fe4dc42ea893daf1866fcbd22f1a911646ac","datavalue":{"value":{"entity-type":"item","numeric-id":4925263,"id":"Q4925263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d2f999f61c5178c731290edafef2b50e05582cd","datavalue":{"value":{"amount":"+0.917677104473114","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":"Q2515582$10CA62BD-017A-48FC-B86A-DA1886F5DB44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f042252decea2598d4b7b3c57d4acfed66fa259","datavalue":{"value":{"entity-type":"item","numeric-id":1764805,"id":"Q1764805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fd31f5acfdb7b5917567ec4b7f37550f98c2035","datavalue":{"value":{"amount":"+0.8064221143722534","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":"Q2515582$61F64DA0-84A6-4A79-AC33-109726565D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcfac382dc417b30119fb5e82bfb42454c3e6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":906379,"id":"Q906379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7dbdbb61ab507426efe9830202a8eff00e0a56cc","datavalue":{"value":{"amount":"+0.7697766423225403","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":"Q2515582$509F9B46-556E-40D4-A083-64A8A4417E86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcf2f66ccea168a9e1317cb56e724ea8cf298c4a","datavalue":{"value":{"entity-type":"item","numeric-id":482282,"id":"Q482282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17dae246b71bbf0316c540d67a8bdef9f9b91ed9","datavalue":{"value":{"amount":"+0.763281524181366","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":"Q2515582$4C9E6541-09A0-44DD-8CD5-52E6CA166EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"972a084a66ac0fad5f38d0864ba2cae6095935f0","datavalue":{"value":{"entity-type":"item","numeric-id":864136,"id":"Q864136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88e9d88f7b985f41a5d711720378fd82623c98b6","datavalue":{"value":{"amount":"+0.7439771890640259","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":"Q2515582$A8FE9CB0-B1BD-4817-8FBA-0262B42620CE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing the directed Cartesian-product decomposition of a directed graph from its undirected decomposition in linear time","badges":[]}}}}}