{"entities":{"Q925139":{"pageid":926987,"ns":120,"title":"Item:Q925139","lastrevid":65444319,"modified":"2026-04-12T02:38:32Z","type":"item","id":"Q925139","labels":{"en":{"language":"en","value":"Fully-dynamic min-cut"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5281488"}},"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":"Q925139$0D9CBEA2-CE15-40A5-A2C8-E4BE75FC2B53","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a92ff7f95565a0e66084515bd910dbca78e8b7b","datavalue":{"value":{"text":"Fully-dynamic min-cut","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q925139$4A6D142C-9417-4C51-9848-0DA505E3059A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c1689f111098873f56b1ef461e84a94277fcee68","datavalue":{"value":"1135.68024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$618E4BF3-3101-42C7-A94B-55414E4C948C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7b9d6ea9c0e72cd3eaf5754418a22b748c7c45ec","datavalue":{"value":{"entity-type":"item","numeric-id":925138,"id":"Q925138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925139$0E28E1C8-1C92-4C87-B28B-FFF4ED21853B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925139$8062A459-B00B-43E9-BFC2-4F86AA3AF522","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6d5ea9744be37dbc33ed76d7f80e76e9dbefcded","datavalue":{"value":{"time":"+2008-05-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q925139$F472283B-6160-4526-8547-34ED5AC01ED2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d698c61396914a77c6ac22cc89ff2d995985bb61","datavalue":{"value":"The paper is about the problem of maintaining a min-cut of a fully-dynamic (i.e. the graph may be updated by insertion and deletion of edges) graph. Its main technical contribution consists of a much more detailed analysis of a greedy tree packing technique, previously used by Karger. Namely, it is shown that in a graph with polylogarithmic edge connectivity an appropriately large greedy tree packing contains a tree crossing some min-cut only once. As the approach allows implementation in dynamic fashion, putting the results together yields the desired result -- deterministic maintenance of min-cuts of up to polylogarithmnic size and randomized maintenance of near-minimal cuts of arbitrary size.","type":"string"},"datatype":"string"},"type":"statement","id":"Q925139$4FB9E5B0-15B5-44FF-A0FD-F3F79FF2CE08","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4418b7d4f2a0250db5c25bb23e561efd56a43eb7","datavalue":{"value":{"entity-type":"item","numeric-id":587571,"id":"Q587571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q925139$066C6EC4-D053-4A41-8C44-757609C430D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$196468AE-E851-4B34-8DA5-9CBB26472DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$BDB1EB05-17AA-4B3D-B504-CAB690E0ED67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$3658AED4-ED8B-4FB9-A66C-E3B78612AF65","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"da2cd50a2b42f8536a037b05ff728db5b2f0face","datavalue":{"value":"5281488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$400B9E54-2BAA-4EE1-8D9F-11C9FC1FB305","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q925139$59165DB8-EA79-4EE5-8EF2-ED53D57D113D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35815417de2ec1f0f5de6b82de9f5fd24d38dc13","datavalue":{"value":"dynamic graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q925139$D0E668B6-DC7B-4857-92B0-1F7F8BCA729E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2eb838beb9d2210dc92355c9fb0f592af31e85","datavalue":{"value":"min-cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q925139$8C0FC741-7D38-4C55-9E43-B53C61352014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bb45071cd7f2ef62e28ce6a67489416cd658ac9e","datavalue":{"value":"edge connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q925139$729887F7-59EC-4522-B802-824D616872A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f21d2d1a13a4f3139d5d0617a37d77de24edef85","datavalue":{"value":"greedy tree packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q925139$79CD9436-A629-4812-8371-03138DF7D3AF","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":"Q925139$FA37770A-5FB6-42B8-A5C2-73B55D902A8E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"371595622f7c48e4e73b31935f2f2acd296d3f0e","datavalue":{"value":"https://doi.org/10.1007/s00493-007-0045-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q925139$5356BDC9-4D67-487A-A901-187ABE284306","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b24a14a9f3aa174e1dd7de277c2d2f2529e061df","datavalue":{"value":"W2611854190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$59CD4DFC-64C0-4AD6-9F50-D945B45CF800","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8d4a5b472d6ed35b85e0d099b614b392c280db9","datavalue":{"value":"10.1007/S00493-007-0045-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q925139$59F64DFF-6C06-4534-9DE7-70DA74FF4FF6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"205a088fddfa11a504fffa007f78b2f8b4a77ca2","datavalue":{"value":{"entity-type":"item","numeric-id":5175972,"id":"Q5175972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e2da6c53f5a750999d81de2cca7409b6fb04c6a","datavalue":{"value":{"amount":"+1.0000002","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":"Q925139$57FC2EEF-F028-4E15-8C3F-129FD1F735E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c187bb605c87bef85fdaba87fddd48cf9656802","datavalue":{"value":{"entity-type":"item","numeric-id":4339009,"id":"Q4339009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d55636cb4121b0626a15f43f86214d76efec395d","datavalue":{"value":{"amount":"+0.8689479","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":"Q925139$324F64A5-78E4-47A7-8861-D56239B17E20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6266a309f551146d55e6bcb19e8e8e06e87271b","datavalue":{"value":{"entity-type":"item","numeric-id":6087010,"id":"Q6087010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"229db61e75ccaaf2c63153972b214ab2b1f9bd89","datavalue":{"value":{"amount":"+0.86046165","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":"Q925139$B140B4B0-FC94-4D8D-A6A9-02B228009C5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b22a61a486fbb45d8c485dd1d149d3d3d42e774","datavalue":{"value":{"entity-type":"item","numeric-id":1905228,"id":"Q1905228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d44c566b0f1d10de9a7c6b119e56f9a5719203f9","datavalue":{"value":{"amount":"+0.8499383","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":"Q925139$1B9DC5DA-4DC6-4C53-A556-EDFBABC79B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ed1e038d5c77eae80ec7b2cf92bc4fea8231286","datavalue":{"value":{"entity-type":"item","numeric-id":715078,"id":"Q715078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59512df2f130cae51c09d323b04bce9d06586853","datavalue":{"value":{"amount":"+0.8492492","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":"Q925139$B4F95E0D-0BB6-4DE5-B798-4D195D8A9917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2f88fa604ad71edb146a02df7daa77fdb36eb80","datavalue":{"value":{"entity-type":"item","numeric-id":5874530,"id":"Q5874530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e005fc595abf590d04c88e8142a12f72214a5724","datavalue":{"value":{"amount":"+0.84706056","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":"Q925139$4369E534-27FC-4B3C-A4EC-C15014585486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a09d259c81bf688210ba844b45daf8b192663906","datavalue":{"value":{"entity-type":"item","numeric-id":1317480,"id":"Q1317480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8ac2cf8a80a61fb77c8247c0a5b0233d5d164a5","datavalue":{"value":{"amount":"+0.84685075","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":"Q925139$98EF23C0-19AD-4B13-9199-0F981D9E5AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14efb3ddfcd777e3ba1c2695dcb17de44fbfae34","datavalue":{"value":{"entity-type":"item","numeric-id":4228454,"id":"Q4228454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b18585845874319d689eeceee802144ec286e5e","datavalue":{"value":{"amount":"+0.8452966","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":"Q925139$28468F04-B7AA-4A71-BCFF-9619CEDF1C52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3e8cf194d77bdf3f310901be3c168aaab8b5759","datavalue":{"value":{"entity-type":"item","numeric-id":5251640,"id":"Q5251640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f47403bf33aaf98a137a30d45cf231266494fbf","datavalue":{"value":{"amount":"+0.8452636","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":"Q925139$6ECFC37A-C404-4A10-8994-7969F02C8D4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"864af2d4be48388e4fe84a89691d71b0b9c4fcf8","datavalue":{"value":{"entity-type":"item","numeric-id":4629534,"id":"Q4629534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abfa97123a78bd95d7a44d2ce3b7ff0dfe5348fc","datavalue":{"value":{"amount":"+0.8441813","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":"Q925139$106E75FF-F2D2-485C-8CC8-3AD9BD3045FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fully-dynamic min-cut","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fully-dynamic_min-cut"}}}}}