{"entities":{"Q1294685":{"pageid":1305435,"ns":120,"title":"Item:Q1294685","lastrevid":67288665,"modified":"2026-04-12T16:37:47Z","type":"item","id":"Q1294685","labels":{"en":{"language":"en","value":"Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1323016"}},"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":"Q1294685$C9A70040-AA7A-48D3-9151-9DB85A0D7238","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f7d88e50dd5d908fab34c7bafe21b2db0390640","datavalue":{"value":{"text":"Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1294685$B5ABB722-BD3A-4605-9277-6402CF31E954","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6770414d393200fc1f9903c969916518d5a5ec16","datavalue":{"value":"0941.90012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1294685$4EB5CF34-F8C6-4299-BDB9-6BA3208EA7EF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b71f9f009d4daff8aaf00ef8ef41fc89f915d6a","datavalue":{"value":"10.1155/S1024123X98000817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1294685$2DCF8A46-B1AB-4157-881A-909EB5A7546C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e05e3a453ae1c27eadbeadc3637f886dcccaddc9","datavalue":{"value":{"entity-type":"item","numeric-id":1294684,"id":"Q1294684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1294685$F0FA7885-2D9A-4698-A21B-CC64A9C12EA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d63a08d80e4eb0dac2bd3b9b4820e060dea00045","datavalue":{"value":{"entity-type":"item","numeric-id":1823165,"id":"Q1823165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1294685$2C756435-5097-49B7-856D-4794D15E565F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1294685$24B26E74-F3EC-4B11-A3E6-E7F4145113E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6da5897752baf69b99419d77cbb1993c9a95d125","datavalue":{"value":{"time":"+1999-08-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1294685$DEA54F80-D95A-48D4-B3CB-5D1E5D9BB74F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"95e949c535c5e828edb95ddd5518153628d2c494","datavalue":{"value":"https://eudml.org/doc/48486","type":"string"},"datatype":"url"},"type":"statement","id":"Q1294685$6C36468C-AEAC-4D2B-A406-0AA92328F8C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"495106a2dc0c4e8a665f4991e4a11808690ddf8b","datavalue":{"value":"Summary: Reliability is an important consideration in analyzing computer and other communication networks, but current techniques are extremely limited in the classes of graphs which can be analyzed efficiently. While Gilbert's formula establishes a theoretically elegant recursive relationship between the edge reliability of a graph and the reliability of its subgraphs, naive evaluation requires consideration of all sequences of deletions of individual vertices, and for many graphs has time complexity essentially \\(\\Theta(N!)\\). We discuss a general approach which significantly reduces complexity, encoding subgraph isomorphism in a finer partition by invariants, and recursing through the set of invariants. We illustrate this approach using threshold graphs, and show that any computation of reliability using Gilbert's formula will be polynomial-time if and only if the number of invariants considered is polynomial; we then show families of graphs with polynomial-time, and non-polynomial reliability computation, and show that these encompass most previously known results. We then codify our approach to indicate how it can be used for other classes of graphs, and suggest several classes to which the technique can be applied.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$3C6F3852-7AF2-40FA-A42D-5673063518C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1294685$732D7557-FAA0-45C5-BBAD-F764B2D43E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6cb186f7c907ca60893d849df7e69a98dd343f1b","datavalue":{"value":"90B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1294685$8C40B05C-074F-4724-AA77-941A311FB528","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5e20c282d05fd52ddf7e3fa163f9eacc67966610","datavalue":{"value":"1323016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1294685$4FB6E3A0-17EA-4C6B-9135-EBB32A4A99B6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$9B762682-CADF-4014-B931-D6751DF4E223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6b49e504becd01906c23fed7912a77c721632ab","datavalue":{"value":"efficient recursive algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$FA3623AE-9CE2-497F-9C69-3E9346FCB102","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"322e81307d2b59f8312b677cec0801774fd4d8e5","datavalue":{"value":"networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$9BCC3A7A-EF74-4A43-8F88-97BFE846CE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cfc79edf190778c24fdbd9385cfe925d57fbdd6","datavalue":{"value":"reliability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$1757CE37-C138-48E8-B518-08B8897F69E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89c7b74075c02a9f90535ca1118f6218f248cc31","datavalue":{"value":"threshold graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$2F7DCE13-918D-49DD-AB3C-93AB206748F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9e0c2719521ea69918eb53b05fb5c5b5235d295","datavalue":{"value":"Gilbert's formula","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$8B371BA1-CA1A-4C8B-9927-747799B7E701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$0CA76CE6-646E-4585-8ED0-1AF67941FFF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b38271a51468d53c7e81b95d4a5ce256f1c20912","datavalue":{"value":"polynomial-time computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1294685$0C01443C-F830-49D4-BAFF-677D8E78BF9D","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":"Q1294685$C07B40D6-D85B-43AE-843D-D6B8B5713EA9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"97c2ecfed663e529d02294822af02ea666321086","datavalue":{"value":"W2056076594","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1294685$9AAFCF0D-7282-45FF-A8B3-C4884399EB47","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44c894dcdafea5d71b9e9ac1f41b6e75033bda97","datavalue":{"value":{"entity-type":"item","numeric-id":3745304,"id":"Q3745304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f414f5c5436c2c13d8c2d33f4748c4023961b6ef","datavalue":{"value":{"amount":"+0.8875523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$6CDF3099-83DA-4586-A3BD-37A9DFF67A98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17c91079b714bade786af464ad986c0e3362f9b4","datavalue":{"value":{"entity-type":"item","numeric-id":3734148,"id":"Q3734148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d43be2601a7882b950d1d05beb80ecbfba313e3","datavalue":{"value":{"amount":"+0.88438","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$7505432E-26A0-4D60-B030-7D56382BC1BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c727d4d76e9a1c0a038fa381181f59632e2bf50","datavalue":{"value":{"entity-type":"item","numeric-id":650005,"id":"Q650005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44bb5f4ab2aa8407ac7bd70c814c81a6afefd4bd","datavalue":{"value":{"amount":"+0.8768409","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$FFF44618-9F14-4176-991B-F87B925A823E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8184c54733c6a44f92c62fc9d5b11ddf6e7dca10","datavalue":{"value":{"entity-type":"item","numeric-id":4470488,"id":"Q4470488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2770b9e2b9ba5c424bc8c62683fdbecb74ea5d8","datavalue":{"value":{"amount":"+0.87322927","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$3D4FD9EB-1982-42C9-8006-5996AFE3B368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97d99afddf2ad2cefb1ce82f9e48c3f471c05394","datavalue":{"value":{"entity-type":"item","numeric-id":1405574,"id":"Q1405574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3627c0712b17016b0455de4acb3b1f1b8289737b","datavalue":{"value":{"amount":"+0.8701091","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$C6F0EBBF-A549-4D1B-B6A1-50A0906758E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf20e98a326319a6295a5b98f074795872facafb","datavalue":{"value":{"entity-type":"item","numeric-id":477692,"id":"Q477692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03e1058f4844f8570a3f81ead9ecf67059a1ff53","datavalue":{"value":{"amount":"+0.86621296","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$85A3895B-B205-44A6-916D-6502215D7CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca64ea138f4e67be614aea4b203498f493590b24","datavalue":{"value":{"entity-type":"item","numeric-id":3052567,"id":"Q3052567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6bf2aa9d5c0c7bf7b26b7f4ae9db0c414c030ca","datavalue":{"value":{"amount":"+0.86297756","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$B5FFFEDD-CBE7-4556-9DF2-040255B38949","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"daecdb7d433a9028bbf185889a57bc8abc256d84","datavalue":{"value":{"entity-type":"item","numeric-id":1919180,"id":"Q1919180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a6ac921571a15d2e37479236461c16ebedaf544","datavalue":{"value":{"amount":"+0.8628929","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$074B8C1B-5AC5-4718-9723-C7C1D74FB095","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2a1ecd997395cad456f671b5fe1851139614728","datavalue":{"value":{"entity-type":"item","numeric-id":3211090,"id":"Q3211090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdad78f2277b60ffb187bda995fa2b372bad6dd2","datavalue":{"value":{"amount":"+0.8580444","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1294685$4D917190-97CC-445A-BB2D-6591631ED889","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial-time computability of the edge-reliability of graphs using Gilbert's formula","badges":[]}}}}}