{"entities":{"Q5918831":{"pageid":8049888,"ns":120,"title":"Item:Q5918831","lastrevid":93474134,"modified":"2026-06-05T04:27:29Z","type":"item","id":"Q5918831","labels":{"en":{"language":"en","value":"Fully dynamic arboricity maintenance"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7203020"}},"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":"Q5918831$A5061745-33B9-4E2A-8A3C-E64D9CCE228D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2e3dc9ab5a31023ec3fd14084b52ffe7863a644","datavalue":{"value":{"text":"Fully dynamic arboricity maintenance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5918831$A0D2C4B8-F9F6-4C61-AEFB-057A244D00EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d0dffdab16fa1f4028b2ca392b9453980a8f63c","datavalue":{"value":"1452.68130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$1624047D-F35A-44D8-8616-5D2CB1ED66D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b9326b694316c8f48c6bba39a5a9132c5169dda5","datavalue":{"value":{"entity-type":"item","numeric-id":1625137,"id":"Q1625137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$0E18DAE3-3336-4858-BEB9-398385D3E204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b996198f60d889c2665626a27c3234f9a40ac7b1","datavalue":{"value":{"entity-type":"item","numeric-id":293161,"id":"Q293161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$10D8C741-43A5-4736-A6B8-26E14957DC68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31c0d4a00f475577a11aceb1985d009cf97e6c2b","datavalue":{"value":{"entity-type":"item","numeric-id":261392,"id":"Q261392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$23F682F1-96BD-4AEE-B38D-F2B64BACFA22","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":"Q5918831$50CE9EF9-E29C-4899-83A1-B4DA2B0FDA43","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d7f157455450e9af34ed66ce1d308afc0b05988b","datavalue":{"value":{"time":"+2020-05-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5918831$A28D3116-F010-4FB2-97FF-C45F8015C727","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b76fa0cfb634ea9e3dfe314a06ec45e42ef6f5d","datavalue":{"value":"The arboricity of a graph \\(G=(V,E)\\) with \\(n\\) vertices and \\(m\\) edges is defined as the minimum number of edge-disjoint forests that the edges of the graph can be partitioned into. The exact arboricity can be determined in \\(O(m^{3/2}\\log(n^2/m))\\) time and 2-approximation in \\(O(m+n)\\) time. There is also an \\((1+\\epsilon)\\)-approximation scheme that requires \\(O(m\\log n\\log\\tau \\epsilon^{-1})\\) time, where \\(\\tau\\) is the arboricity of graph \\(G\\).  This paper focuses on the dynamic graph algorithms. If edges are inserted or deleted over time, a dynamic algorithm maintains some additional graph information which is then used to calculate graph arboricity faster than a static algorithm that starts from scratch. The algorithm presented in the paper maintains a decomposition into \\(\\tau\\) edge-disjoint spanning forests and both insertion and deletion take \\(O(m\\log n)\\) time in the worst case. The paper concludes with an amortized bound of \\(\\Omega(\\log n)\\) for the cost of answering the arboricity query under edge insertions and deletions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$CE7279D7-9780-4CD2-9D78-C32104141461","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":"Q5918831$BB0BACB9-1072-4287-80D4-B0EAA0A4B619","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$098C274E-C0C0-41D5-ACB3-DC059280FC24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$ACF1BA8C-4438-49BD-BB3D-A3396AE5FF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$384441D5-BE13-4234-9830-41D82D464E2A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7781879742100221445a4d2be374b786022b5068","datavalue":{"value":"7203020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$74F7A503-C594-4E6A-AC66-EBBA398A5A09","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33d42ddf4e1ea41f5d8846555ec9a668fbb0211f","datavalue":{"value":"arboricity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$550430D3-261A-434E-857E-BC08A10C6E83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"500bce71eeed4de9f5f4325febb3e9ee8b213c9c","datavalue":{"value":"fully dynamic","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$06F83340-C8C3-4BA6-A6B5-D7B8B42CD587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10073d731ebd75f6f9a6ffd3abe95b2de4890d33","datavalue":{"value":"augmenting paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$FEB23D6F-7332-459C-9930-D5A7A8D66E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d280128f2303f021a1accdf268261ee918b55c21","datavalue":{"value":"incremental","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$4117C403-6884-4B51-B4A4-3191D4521607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2254f243b6facc913985c260850bb9d36d17ca55","datavalue":{"value":"decremental","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$7883B31A-2BE5-4EA5-BEE2-B517C71050C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918831$D0EAF44C-459B-4525-9BC6-B7A3C39502A1","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":"Q5918831$F819BA33-B800-494B-AF84-26C288FDCB19","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"189f45d1af7cb788a308e022dddbd4a6cfed381d","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2020.04.010","type":"string"},"datatype":"url"},"type":"statement","id":"Q5918831$058B5F23-ED12-42E6-901B-044A837F68F9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cd5a0d0f75cdce5e6273e6a9a5dec97d206c0665","datavalue":{"value":"W2963057705","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$E0A806FD-9AF0-4DF4-8115-8596DC52DB57","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b52b051f0f09a209fec5ad767532fa0a732fa13d","datavalue":{"value":{"entity-type":"item","numeric-id":5919441,"id":"Q5919441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$AAA31AC8-4FF6-4490-9001-3C47B995F3C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29483a98ecd0d8daf6a0d01721150dcbc47f716b","datavalue":{"value":{"entity-type":"item","numeric-id":5136228,"id":"Q5136228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$AE74557D-73BF-4E6F-89D0-5DCDE73AA9BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7e855485ec60d6bd24b7db7377c33444071740b","datavalue":{"value":{"entity-type":"item","numeric-id":3297754,"id":"Q3297754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$E562B787-EE0D-4BA1-A94C-7176D6AFD274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f600695d8c6c6207c7484fb31dfb63c3c891299","datavalue":{"value":{"entity-type":"item","numeric-id":3024792,"id":"Q3024792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$C1050FB2-85A5-4934-9142-3D46AE89F3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edbf7e284bb86f282deb0fe0b21742f7eb1427c6","datavalue":{"value":{"entity-type":"item","numeric-id":5586414,"id":"Q5586414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$1FA791EF-834A-4B12-9D9A-449908C7234C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"220d4ab4bf1e85d67a96585735c0bcc184d9d730","datavalue":{"value":{"entity-type":"item","numeric-id":5586413,"id":"Q5586413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$BD6140DC-F790-4A54-AA54-E16B242F304A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5286f27dd639d8060d13739dba359dc4b873941","datavalue":{"value":{"entity-type":"item","numeric-id":1334644,"id":"Q1334644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$22BAEAA8-4B01-4205-8D6F-4FC45CF31A06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33d7c422acf2e37b305df099341825656aa639a8","datavalue":{"value":{"entity-type":"item","numeric-id":4377121,"id":"Q4377121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$53B16418-225A-4EF7-A96E-06D107296468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf027cdfa25a184aa219a18a12071891ef869b1d","datavalue":{"value":{"entity-type":"item","numeric-id":1392570,"id":"Q1392570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$35FF09E6-5EF1-4EFB-83EA-DBD51FBA10FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0bc47d3e85841694290d25e087b46ec8a7f400e","datavalue":{"value":{"entity-type":"item","numeric-id":2942621,"id":"Q2942621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$1E0D835E-BE6D-4F37-8F73-EE6746AA50E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072b3268666303260788a4a7f65ee68c47fbdfcd","datavalue":{"value":{"entity-type":"item","numeric-id":5167867,"id":"Q5167867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$DB8249B7-F91C-4A55-83F4-B07654EDF334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d92fff1f5161432271671f29ed2c350d405f9f8","datavalue":{"value":{"entity-type":"item","numeric-id":846004,"id":"Q846004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$AD78A792-F949-4631-9B1E-72B855C039FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"711cb68a3f23253ea3bfc5d62858e204e53a49ca","datavalue":{"value":{"entity-type":"item","numeric-id":3286077,"id":"Q3286077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$1C91C818-619E-4017-BCAF-D325D8F75796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f40f6cac0c780a9b93fef04ad01fbee5da55dc","datavalue":{"value":{"entity-type":"item","numeric-id":5731396,"id":"Q5731396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$47B92A74-D156-4DA1-BF43-EC28BA9DA4E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef4ddf07e47c9caa299c7b6b22068bcb9defbaf0","datavalue":{"value":{"entity-type":"item","numeric-id":5470720,"id":"Q5470720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$71D4D8EF-21C9-4E74-87CB-1484BB834BB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab5ddb731ba675301e5048bd2f92238fb789a312","datavalue":{"value":{"entity-type":"item","numeric-id":3705239,"id":"Q3705239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$05DA8F1E-9836-4EC8-A394-D16FA6FFAE31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36313581e6a77d3533a1cd4630fd340bdc11d5ec","datavalue":{"value":{"entity-type":"item","numeric-id":1121926,"id":"Q1121926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$62C84F91-26FE-43C1-BA1A-4708B1DC1E23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b76c498f5c4968b18e0a5cf8a7bb4513c31822","datavalue":{"value":{"entity-type":"item","numeric-id":1838310,"id":"Q1838310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$6FD105E8-F98C-4FE3-93E7-7067039C0AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdb68a6c93b064efcfd440472a9055852b0c2ec","datavalue":{"value":{"entity-type":"item","numeric-id":3275433,"id":"Q3275433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918831$95140E35-45E9-4541-B929-7B26E81B3197","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ff6b1d3248f6c89af44e6a8f93641c0f30dd6869","datavalue":{"value":"10.1016/J.TCS.2020.04.010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918831$CEBD646E-E316-495F-A360-7CC582272607","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"731949d0f3c5ff24fc49f9ede2e1c63e853e9487","datavalue":{"value":{"entity-type":"item","numeric-id":5919441,"id":"Q5919441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e80a914a9ffc1f3e25dc6285346f8ce9b918720d","datavalue":{"value":{"amount":"+0.8793537616729736","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":"Q5918831$9FE374EB-6B76-4B2C-8C4E-009952A1B1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84a6ad26042337329dfe12f655a0b1a59bd40585","datavalue":{"value":{"entity-type":"item","numeric-id":4542523,"id":"Q4542523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3983b66f2c4ecf5ae57c4b3ff1f6913c0faa0531","datavalue":{"value":{"amount":"+0.7556101679801941","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":"Q5918831$C95E70AE-C72F-4118-9F1E-E06033E3AADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a73075c9cca9807096b75cb5922e05ce8943f2b6","datavalue":{"value":{"entity-type":"item","numeric-id":418737,"id":"Q418737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"408dc47fc969d77632370508b7a7b96541497443","datavalue":{"value":{"amount":"+0.7552410364151001","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":"Q5918831$8CC1919E-4411-425A-8D6D-B3A23C05AD27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"989d075d82c27aed283db93b5023dbd11f16cbd2","datavalue":{"value":{"entity-type":"item","numeric-id":5441357,"id":"Q5441357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bfe0de1a2494984c7b62d643c33ea47851c1b42","datavalue":{"value":{"amount":"+0.7507361769676208","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":"Q5918831$CC8E8AE0-638F-424B-97AD-93BC223DB876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5424eb96fbe07a88a62adab1f3f5d213c87c1095","datavalue":{"value":{"entity-type":"item","numeric-id":4230327,"id":"Q4230327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9b555b4fb7720b06e904e737d0ba4d2539afd5e","datavalue":{"value":{"amount":"+0.7405207753181458","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":"Q5918831$0087319A-4928-47E3-9C0B-A41F1AAF745F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fully dynamic arboricity maintenance","badges":[]}}}}}