{"entities":{"Q1921328":{"pageid":1932070,"ns":120,"title":"Item:Q1921328","lastrevid":69306834,"modified":"2026-04-13T06:07:46Z","type":"item","id":"Q1921328","labels":{"en":{"language":"en","value":"On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 915390"}},"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":"Q1921328$DA90D0F5-0A17-44ED-8C76-B539C18CB86A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4f987cb8c035ebb5b6ef0919c49b477733d1d80","datavalue":{"value":{"text":"On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1921328$A17E2634-0785-410E-B284-3A3F3F062DE3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"268ed8a18d8b9f182f55665c60b9a51b0fbabc62","datavalue":{"value":"0861.90119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$F2BF9818-7C5A-403D-B7F6-0B202CAF6CF5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a340d39aa323fd5c88ab553d22937b4995258413","datavalue":{"value":"10.1007/BF02141748","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$91036A7D-3B81-4D6D-B6A8-3EB0649AB82F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"848e2bb4aad94efb584ba564a291dc127cb5849a","datavalue":{"value":{"entity-type":"item","numeric-id":676929,"id":"Q676929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$8592C986-8659-4192-A8A3-FE7B8DEEE2A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3fe92f81d384032f9bc19a87027ed68c63cd8aaf","datavalue":{"value":{"entity-type":"item","numeric-id":1667671,"id":"Q1667671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$85EEAC01-FAA2-4145-84E5-341EB077790B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"95f4a47752e6dde2f4d6f910dcba94ba8b5377c0","datavalue":{"value":{"entity-type":"item","numeric-id":57895,"id":"Q57895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$8FA3B93A-B458-4203-B9C7-D5B2D2E3EDB5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a84f04e4f8be60b757ec22b6381c46df11b7f97b","datavalue":{"value":{"time":"+1996-10-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1921328$5B91DF05-80B1-48CF-8813-CFD363A909FB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6526aa7eefcdd2f9520553cdb6891aa822663f07","datavalue":{"value":"The authors present a heuristic which approximates the \\(p\\)-edge partitioning problem for large sparse graphs with a connectivity constraint on the subsets. It is decomposed into two parts: the computation of an initial partition and an iterative retrofitting process. For the initial step the finiteness and correctness is proven and it is showed by using front-based tools that its complexity grows at most linearly with the number of edges of the graph. For the retrofitting method again based on front techniques a new balancing step has been designed in order to reduce the number of iterations. To illustrate the quality and speed of the heuristic a few examples are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1921328$37061D74-9C84-48C3-93AC-BDBF112C579B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$2CFD4899-C0A8-4E80-90C0-1A9E346CFA13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$1CE70C18-B223-42B9-9022-3C5302EB56E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$8FB6D7EA-E0A9-4647-B5AD-EF834A42490E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$19805396-CD39-4F61-9BA9-23A1E14F560E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e16ce449e3376b6c894cb1e811ac0e0125d73888","datavalue":{"value":"915390","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$AA838C10-068E-49BA-8396-DCE0588428F3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1921328$04ABF764-5FAB-4053-B3A1-38F4B1917AA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ba15923b1b6c0cf211386744ba263db8b20e726","datavalue":{"value":"\\(p\\)-edge partitioning problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1921328$C7E7757F-4228-4538-A5C5-09D5AAB45ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5dd4044a9656a43d237b2cdf91f60682427ad4ba","datavalue":{"value":"large sparse graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1921328$9F1E998C-27B7-44DD-A3A2-854736A7C082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3250e4d3348da690e7b91e3cc8fcad2e11f794e1","datavalue":{"value":"connectivity constraint","type":"string"},"datatype":"string"},"type":"statement","id":"Q1921328$D4B62500-77FF-4995-B544-6957BA133683","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":"Q1921328$042A05DE-90C8-4E27-9148-0DD9E536AB6B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"08df152080249f51aeb11009adb6df7d097b7d34","datavalue":{"value":{"entity-type":"item","numeric-id":4740598,"id":"Q4740598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$38C82857-2D88-4701-9AC0-64DBC1677990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"995f3d0e21cb6132e6a7dfc3313fc18917a919c4","datavalue":{"value":{"entity-type":"item","numeric-id":3802647,"id":"Q3802647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$97805663-624E-48D9-A0E8-56A2E820648A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d97c280be41be0d4b327a4beeffb546a06614104","datavalue":{"value":{"entity-type":"item","numeric-id":4083702,"id":"Q4083702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$22A37B44-2792-41F2-A091-221580764BF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b978709a654c254a17ab7ff5ba398a44d607d3c4","datavalue":{"value":{"entity-type":"item","numeric-id":5682350,"id":"Q5682350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$55305986-9AA4-4DEB-9D60-42C92671AEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53c8c8a75f99529295ff252dcde53d117de4e485","datavalue":{"value":{"entity-type":"item","numeric-id":1189421,"id":"Q1189421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$11327C9E-84E4-4A2F-8F3F-555D0C41BAD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"352b33bd7bedec9a5caebd970d73a33c036faf67","datavalue":{"value":{"entity-type":"item","numeric-id":4195885,"id":"Q4195885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$E5DFA783-0B41-4E9C-B7FA-D130D7F1831E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be656917aa59c89f859f0ed199c711c371d7f1f8","datavalue":{"value":{"entity-type":"item","numeric-id":4763752,"id":"Q4763752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$BFAB9599-C985-4724-A761-82FF30CD58B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a44f31abbdd4dc84e5f661896a7812e44411ddf","datavalue":{"value":{"entity-type":"item","numeric-id":4100093,"id":"Q4100093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$FA31B126-9DFE-47F0-9482-8A5EC1FA5163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5338aaf45ec289c0528b23d10f09acf085d8a042","datavalue":{"value":{"entity-type":"item","numeric-id":4371622,"id":"Q4371622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$A70B5943-68FB-4D75-B348-35BCA3B6A0F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0edaa671d985ed50d6c44012efdef4b1b668dfde","datavalue":{"value":{"entity-type":"item","numeric-id":4288580,"id":"Q4288580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$747D1A13-A3CE-47D5-8235-2B7729B0C92D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3745c84a6fa05e578321e3dbff91c36fa6e5263c","datavalue":{"value":{"entity-type":"item","numeric-id":3495536,"id":"Q3495536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$A757C208-03EC-450D-A549-58F07445914F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14fb0962ec1970cd24de49d8536c8bbd1a39fa82","datavalue":{"value":{"entity-type":"item","numeric-id":1904714,"id":"Q1904714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$B2CB6089-D93A-444D-A4B0-192610718ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e17921847cd8c2151c3cb2c5de7054949eb4e0f","datavalue":{"value":{"entity-type":"item","numeric-id":3765553,"id":"Q3765553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1921328$D51982B1-EBED-4833-843D-A013AECEDF80","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f4d42ff70d13404d4a63e51bef03af454871c61","datavalue":{"value":"https://doi.org/10.1007/bf02141748","type":"string"},"datatype":"url"},"type":"statement","id":"Q1921328$861D68F2-3643-4BF9-B0DB-C2C771A35357","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a3bd266e5886fad6b9473c199415b9e9c8b45bf8","datavalue":{"value":"W2064880188","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1921328$D4378F6E-BA84-446A-BB05-049A5866C64F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"726d6434b397b3565b3f24d892718d22e19af4a7","datavalue":{"value":{"entity-type":"item","numeric-id":2467568,"id":"Q2467568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d283dc35340d8d887674e9d771d128893620157a","datavalue":{"value":{"amount":"+0.7938845157623291","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":"Q1921328$2033F74F-8A67-4708-976C-FEB3B7222B62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"796048930c70350b7dbdd80a898547320d27939e","datavalue":{"value":{"entity-type":"item","numeric-id":3158904,"id":"Q3158904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67245eeb9352d4e09e251d2e1ef2d8a934754385","datavalue":{"value":{"amount":"+0.7451359033584595","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":"Q1921328$21E2C5FA-2838-498B-A7D7-7C03B1E0E584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"452b0078566ccee2224bd885869d42fe8b10b0f1","datavalue":{"value":{"entity-type":"item","numeric-id":3086673,"id":"Q3086673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52aa039af51fd67416ec5918422ac61d339ea014","datavalue":{"value":{"amount":"+0.7435581088066101","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":"Q1921328$83EB12F4-CFB0-4101-B6AF-96A862D0ED56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be55c255812c7f030b47be22134c2116d4e7a7ae","datavalue":{"value":{"entity-type":"item","numeric-id":4038712,"id":"Q4038712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2d55e5662f35d58044accc09954b50fdd30b50f","datavalue":{"value":{"amount":"+0.7415686249732971","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":"Q1921328$CE0C43F3-4173-4607-80CB-32636DC96E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4910ca0cbc6fa06eb0371719398d52e56c531ce5","datavalue":{"value":{"entity-type":"item","numeric-id":5432325,"id":"Q5432325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e44cb77b0f6516bc1bf2e4d52f3274e88585387a","datavalue":{"value":{"amount":"+0.7403222322463989","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":"Q1921328$4DBCD7F2-6DB0-413B-9869-1FEED589AB71","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_validity_of_a_front-oriented_approach_to_partitioning_large_sparse_graphs_with_a_connectivity_constraint"}}}}}