{"entities":{"Q2347799":{"pageid":2358542,"ns":120,"title":"Item:Q2347799","lastrevid":52277027,"modified":"2026-01-21T08:24:08Z","type":"item","id":"Q2347799","labels":{"en":{"language":"en","value":"Faster exponential-time algorithms in graphs of bounded average degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6444000"}},"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":"Q2347799$13A0FB59-6A36-4E9A-AFF6-21CD968B9BBD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3954736056deb49c8e7ceae729d10872390984a","datavalue":{"value":{"text":"Faster exponential-time algorithms in graphs of bounded average degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2347799$FABB3C59-9AB1-4C61-969A-72B7ED428ED2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0588be051544c3066916e8f4b698298ad5e5a390","datavalue":{"value":"1334.68095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$3DFCDF73-12FC-4205-B4C1-C67C0C17BFDB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"126ad086c11d29b44b6dea551efd67f8beb1ce87","datavalue":{"value":{"entity-type":"item","numeric-id":255282,"id":"Q255282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$C44512B1-A52D-41CF-B2BF-D357BE8A7E96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8393ad112fe8548ea40a3793cd450c8b7586360e","datavalue":{"value":{"entity-type":"item","numeric-id":255284,"id":"Q255284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$5840A763-1129-4254-8923-D521F8A49859","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$854B1CCB-B6C0-46AA-BF7B-733AC3209418","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2cc2e549e7abe5b2e4af58c8f5718fb16ed95289","datavalue":{"value":{"time":"+2015-06-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":"Q2347799$C4A6517B-666B-49E1-A19F-E82C56DD3A3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e478f511d39d50f99a9d37d34594a8629fca81a","datavalue":{"value":"The paper provides a simple algorithm that computes a permanent of an \\(m\\times n\\) matrix over an arbitrary commutative semiring with at most \\(dm\\) non-zero entries, \\(d\\geq 2\\), using \\(O^*(2^{(1-1/(3.55d))m})\\) time and semiring operations, improving and simplifying the recent result of \\textit{T. Izumi} and \\textit{T. Wadayama} [``A new direction for counting perfect matchings'', in: Proceedings of the 53rd IEEE annual symposium on foundations of computer science, FOCS'12. Los Alamitos, CA: IEEE Computer Society. 591--598 (2012; \\url{doi:10.1109/FOCS.2012.28})].  Next, a simple algorithm for counting perfect matchings in an \\(n\\)-vertex graph in \\(O(2^{n/2})\\) time and polynomial space is given. It is based on the observation that the problem of counting perfect matchings in general graphs can be reduced to a problem of counting some special types of cycle covers. The provided algorithm matches the complexity bounds of the algorithm of \\textit{A. Bj\u00f6rklund} [``Counting perfect matchings as fast as Ryser'', in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA'12. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 914--921 (2012)], but relies on the inclusion-exclusion principle instead of algebraic transformations.  Finally, two combinatorial lemmas are shown that bound the number of ``Hamiltonian-like'' structures in a graph of bounded average degree:   1. a minimum weight Hamiltonian cycle in an \\(n\\)-vertex graph with average degree bounded by \\(d\\) can be found in \\(O^*(2^{(1-\\varepsilon_d)n})\\) time and exponential space for a constant \\(\\varepsilon_d\\) depending only on \\(d\\);  2. the number of perfect matchings in an \\(n\\)-vertex graph with average degree bounded by \\(d\\) can be computed in \\(O^*(2^{(1-\\varepsilon^\\prime_d)n})\\) time and exponential space, for a constant \\(\\varepsilon^\\prime_d\\) depending only on \\(d\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2347799$F921ABF5-1159-4C88-8719-AE80925901BD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d7f1127c63fcb04479eae252afd6f073fe30fe10","datavalue":{"value":{"entity-type":"item","numeric-id":187117,"id":"Q187117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$A16BA183-8748-4CB1-9AC2-044DD0D672F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$CC6CEB37-5722-4AB4-A643-B27C4B1F636E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$2C130BA4-D029-4C5C-82EF-8CFA57EE0272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$23E730E6-8ED0-4115-BB06-82DC34662ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$120CFDA9-3CF0-4307-A66F-80D675ADB697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$DA5D701C-101F-4723-8A55-68698A62380B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ce4e6cb55133720c8363e32b77f36351f1bc2d6e","datavalue":{"value":"6444000","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$14B0BF90-60CF-4EAF-B137-EEC992FF38DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ad6de629ac8fa71c1138c4b1cfc6f9f4b51f811","datavalue":{"value":"moderately-exponential algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2347799$AA124B27-83E6-4E9E-9193-D954CF4E431E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abdcffd377d27b9ec72bec0ea8183b65c53ecfac","datavalue":{"value":"bounded average degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2347799$50DD341A-E0E1-45C5-9D9E-E1F4E414CF10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffef4ef77fa7f2dda4da93846354c0c5b3e1bb72","datavalue":{"value":"counting perfect matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2347799$74C306D2-3156-410C-9CE3-8F485A2EF48A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f260477d4659bb2e04902d6481c6353c22b3a4f1","datavalue":{"value":"minimum weight Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2347799$2528324F-4966-4AA2-AB9A-42347810A8E5","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":"Q2347799$16FEAFE6-9EEF-4AA4-BBD9-3E08AA21C402","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3088f2c06f321f85084ff157daf3c72aa16193e3","datavalue":{"value":"https://doi.org/10.1016/j.ic.2014.12.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q2347799$4EAD801C-99B6-4CF7-903E-A82DF442B42D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c772aad5733b05df43dc184e07695e415608a872","datavalue":{"value":"W2950262288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$20315AF3-75F6-46AA-85CA-E759B685CC7C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba453736f5070f55cd4d267ba0cf61a80c0cfc6e","datavalue":{"value":{"entity-type":"item","numeric-id":3292043,"id":"Q3292043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$80073DB8-7706-4630-8C74-AC33054A0AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$9C19E10A-5E0C-47F8-8672-EF3316B9AD94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0f92064a7c0a7169d569584bcfda37a7842df61","datavalue":{"value":{"entity-type":"item","numeric-id":4414647,"id":"Q4414647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$FBC078CA-CC2C-4795-9460-F6B9609A0CBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf4ef2a1a38b56c81df266118bb63175df99c046","datavalue":{"value":{"entity-type":"item","numeric-id":3851094,"id":"Q3851094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$6C86522A-FB83-46A2-98A6-03937ECD3ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e180dc57e4524eae2fb98685498e0629e92cfdb9","datavalue":{"value":{"entity-type":"item","numeric-id":5743447,"id":"Q5743447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$CE20BF33-E9BE-4893-A018-9D2E5891EE25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"112fa1e16c28072d1b690d88a68f10e9a878f19f","datavalue":{"value":{"entity-type":"item","numeric-id":5943094,"id":"Q5943094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$E9DBEFB5-95D7-4472-B148-8626A77C99A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5762d647bad67eb99de6bbf40a6d31cb9ada3a18","datavalue":{"value":{"entity-type":"item","numeric-id":5365080,"id":"Q5365080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$0BFBF2F4-1F14-4073-B475-4ABE3DD4EFE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4226e3e65547158ea8072512457653ecc8bcdac6","datavalue":{"value":{"entity-type":"item","numeric-id":5417690,"id":"Q5417690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$9B951D9D-E64E-4CC0-A9FF-DF47687549DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32937fb1f3d2d7b266e1ea8a71edd09deb33fcdd","datavalue":{"value":{"entity-type":"item","numeric-id":5956839,"id":"Q5956839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$0C284ED6-F794-4A54-B53E-7F14E1309388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9de489b9c0512a2192710e064751eb7fc898f6cb","datavalue":{"value":{"entity-type":"item","numeric-id":1044712,"id":"Q1044712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$26205253-AC8F-4485-81C4-F0B1E3A1DEA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbe031082d2fbe030c2b0d05fafea0366b1dad29","datavalue":{"value":{"entity-type":"item","numeric-id":407582,"id":"Q407582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$D54A4B83-2261-4EA8-BC35-706689BF8F88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e499f0b3beca4ddc75aa026fbc706daa8f56ce95","datavalue":{"value":{"entity-type":"item","numeric-id":958212,"id":"Q958212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$BA7E7B3C-7694-40BE-BE22-AAFF31E63E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67071b92c641b61d252a6aaf439c552c583b76f","datavalue":{"value":{"entity-type":"item","numeric-id":3656867,"id":"Q3656867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$F87EE15D-0AE1-4102-BE82-7B58F738E96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da035103000af3f74691ea60249af57559c987bf","datavalue":{"value":{"entity-type":"item","numeric-id":3189059,"id":"Q3189059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$774AB6EA-2898-473B-9D9F-370DA7AEE99F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f6f0e024114319e5eb6aae9883a0233df2f35ab","datavalue":{"value":{"entity-type":"item","numeric-id":3549598,"id":"Q3549598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$B0AA72EA-9B1E-4EFE-9AF0-E751B53657EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d1d5f4e43f160c57c58d120a935d48abc9b7662","datavalue":{"value":{"entity-type":"item","numeric-id":1959390,"id":"Q1959390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$5C6C3768-9443-4ED0-9AF9-A09496914CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"798f2dfde98c9fa8b3b3a30f83ee8a3de05fcab5","datavalue":{"value":{"entity-type":"item","numeric-id":5167772,"id":"Q5167772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$442AF9D5-AB66-44F9-A693-670309EE7FB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d078e21f9718b01f228742d1c2f5371b675a0f5","datavalue":{"value":{"entity-type":"item","numeric-id":3558013,"id":"Q3558013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2347799$7A2F3DB4-3045-4C06-AC43-6F19BFA41E5A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"483b5c1a2e61e330732045e89e9d8a780861a8ea","datavalue":{"value":"10.1016/J.IC.2014.12.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2347799$FD12557B-29ED-46D1-A5AB-BD87F43B3300","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43f377c66bfc43b68bc92c2d0c5a99d533ec47d7","datavalue":{"value":{"entity-type":"item","numeric-id":5326575,"id":"Q5326575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c7583ac5d10921e45d9830a5768cb0786bb2cd8","datavalue":{"value":{"amount":"+0.936116635799408","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":"Q2347799$CA20CC5B-4FCE-4854-AF41-17B39EF3EBF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9389aa04ade2890e4f21ede4c760acad33fb224a","datavalue":{"value":{"entity-type":"item","numeric-id":5743447,"id":"Q5743447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6764181b3b0593c21e7174e7084bdc9ae928e939","datavalue":{"value":{"amount":"+0.8242998123168945","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":"Q2347799$6DCDB370-DCAB-43C3-BD66-3859052CF6CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0865ec8169d4f806bb01b9979cb6cb58bbaee6d","datavalue":{"value":{"entity-type":"item","numeric-id":5194650,"id":"Q5194650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"073c3640e39e00b128cbee7ad28c549d71ae9f29","datavalue":{"value":{"amount":"+0.7940990924835205","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":"Q2347799$A64472D0-07FF-480F-8538-0BF91D36A35C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62d0a5857dac8b8ea1074255df0e5afd0db06d0e","datavalue":{"value":{"entity-type":"item","numeric-id":1199692,"id":"Q1199692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c510a45675a12f7da1f80afbec5a8a228b10efa7","datavalue":{"value":{"amount":"+0.7753196358680725","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":"Q2347799$33C10483-0C5D-46BB-AC48-88268DBA28C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ccb525fe3bb09d90251c968bcaa455b45724544","datavalue":{"value":{"entity-type":"item","numeric-id":958212,"id":"Q958212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54562a0ec196353880a6bd18796009cdb635e824","datavalue":{"value":{"amount":"+0.7750766277313232","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":"Q2347799$8285C292-D69C-492C-9E8D-A62F30C926AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2347799","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2347799"}}}}}