{"entities":{"Q810053":{"pageid":811901,"ns":120,"title":"Item:Q810053","lastrevid":49534408,"modified":"2026-01-07T13:33:49Z","type":"item","id":"Q810053","labels":{"en":{"language":"en","value":"Sparsest cuts and bottlenecks in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4212094"}},"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":"Q810053$27A9FA45-E3A3-41AD-A2D8-706185F68EF0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"532d5ceca57b30131f91c4b54ac72108fb72004a","datavalue":{"value":{"text":"Sparsest cuts and bottlenecks in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q810053$9F2ECB1F-E423-4643-B516-A1B2BFBD5ACF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8cb9f25088e29da1ffc8bdcabe9b14f831dd823d","datavalue":{"value":"0733.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$FCE3EEB3-6D4A-4C87-A566-44F8CFEEC050","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2024257593fbfe6aed7da7563519ca8d411af624","datavalue":{"value":"10.1016/0166-218X(90)90133-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$E8AFDC15-8862-4311-A593-47C1B67D86D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb20e067b28976c0bdbb95d56d56ef5c6b170246","datavalue":{"value":{"entity-type":"item","numeric-id":810052,"id":"Q810052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$07AEFD64-8A63-43B9-A2F7-99A0708E71A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"25f1cfa3980c3cfc230dee260e62cad57d59a417","datavalue":{"value":{"entity-type":"item","numeric-id":169303,"id":"Q169303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$B46ED5AE-5035-482C-9437-7F76652B8B87","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$9B0FCE6E-05CF-47C5-84CC-6CEE7776B6F8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q810053$7878220C-A081-40BE-BCD8-6A3D35C50580","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"59f3a52432aaef532819d61ec08aa2f437ee89d0","datavalue":{"value":"It is shown that the problem of finding a sparsest cut of a graph is NP- hard in general. However, certain classes of graphs on n vertices are shown to admit solutions in O(n), \\(O(n^ 2)\\) and \\(O(n^ 2\\sqrt{\\log n})\\) times respectively. The paper goes on to consider the maximum concurrent flow problem. In this problem, cuts with maximum density are termed ``bottle necks''. The near dual relationship between this problem and the sparsest cut problem is exploited to determine a broad class of graphs for which the sparsest cut problem is efficiently solvable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q810053$AD004051-F56F-4AFE-AC83-02B7349C687A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$5A998DC8-82E6-4830-8606-A4AE52A0EBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$D8077AC2-B78E-4094-B5EF-1A548A08E72E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4399edb936883c90e4875bd660b6cebbb734bcea","datavalue":{"value":"90B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$0525C198-C017-43BC-BD94-28FDCEE0C3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$B13E4B4D-654A-4513-9E08-C15E599E2992","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02778c66d72cc461a410b4432e22cdaeb2d2cd4c","datavalue":{"value":"4212094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$0A642803-3D81-4792-A62E-3BB7395F8194","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bceb40919acac93ccebd09734495b9d4d1aeac0b","datavalue":{"value":"bottlenecks","type":"string"},"datatype":"string"},"type":"statement","id":"Q810053$01ADB230-E26F-43A2-BB39-F54DE0EA4224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6bf63861c7b73457c74eae26bb28923489eb81de","datavalue":{"value":"network","type":"string"},"datatype":"string"},"type":"statement","id":"Q810053$003BAF47-3CEB-4A37-8F44-E3FA661DC098","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a90606399a149c55f18a9335c2a7865119eb7561","datavalue":{"value":"sparsest cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q810053$BDF7E858-D792-4310-8C58-B410BB45A004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q810053$4E9DC2DE-68B4-44C7-8613-C4211728FA79","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9dff036c4dcf3bb77a6916d0bddc7faae8fc996d","datavalue":{"value":{"entity-type":"item","numeric-id":189706,"id":"Q189706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$FD7121CE-4B8E-47EE-B893-A3D09E437729","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":"Q810053$8A0E6276-C5FD-4F06-90A0-FF98394D8DF2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$5D6F2022-711D-4479-ABF1-D0E6F9CCE2FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$0642A18C-A86A-48E7-9BF0-FCABE28EBC1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e28d865b6a527d6aef184a58e15bb15ad21dc2c","datavalue":{"value":{"entity-type":"item","numeric-id":3856819,"id":"Q3856819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$9A454785-E598-40A3-8287-1E19232E1ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0711af0bd25d7e9cead76105248e82b5a58f4ccc","datavalue":{"value":{"entity-type":"item","numeric-id":3690541,"id":"Q3690541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$6E364C5E-4FF6-4755-9C5D-9BB45FF18E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c22c7a604714392eecd599544d8c8bb5cb576c9d","datavalue":{"value":{"entity-type":"item","numeric-id":3691767,"id":"Q3691767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$B41BC5AA-2418-4D00-A1E7-50BE4A3DA802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58b75e823d7d97463bea3f1b237ecc88aaa499fb","datavalue":{"value":{"entity-type":"item","numeric-id":3474283,"id":"Q3474283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q810053$EA554B83-E70C-4D7F-A95D-63D9D016175E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9044375bee67a85ecb396d9b42298e313cbc5797","datavalue":{"value":"https://doi.org/10.1016/0166-218x(90)90133-w","type":"string"},"datatype":"url"},"type":"statement","id":"Q810053$B242375F-8F66-4080-AD21-2378215A1CE2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"457765b1dd14b5ae969af98b5e9550a06961ee7b","datavalue":{"value":"W1989720410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q810053$F8886710-F05B-4705-8F41-2803F72835C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"655daa24e2197fb4c7beed855231012c88c50f93","datavalue":{"value":{"entity-type":"item","numeric-id":1800990,"id":"Q1800990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ccd9be9c88a955932eab99159dc0ef7596553e1","datavalue":{"value":{"amount":"+0.862831175327301","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":"Q810053$1D3D806C-D5FA-44CB-8F8B-9A71E0F45D41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de356702e0ccd1ce5da5f71dcedb38ff2ed38d0b","datavalue":{"value":{"entity-type":"item","numeric-id":1427176,"id":"Q1427176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acbab525868998ac0f88be40ae3f3d4fdec0e7f6","datavalue":{"value":{"amount":"+0.852927565574646","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":"Q810053$C0DAFEDD-4A90-424D-ADE6-348FD886414E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db8a0fb4b1133652515606a1e39070259704ca6c","datavalue":{"value":{"entity-type":"item","numeric-id":3186492,"id":"Q3186492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75e208b629e76508ade15b78481c0ae5af055a09","datavalue":{"value":{"amount":"+0.8509340286254883","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":"Q810053$9592E101-BC03-41B8-95D3-3EAE97E2C202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"febf907301d960a4d47f490877155f33cd4df051","datavalue":{"value":{"entity-type":"item","numeric-id":3000501,"id":"Q3000501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba2ba098ea139838f96bf6a25009f833a535cdcd","datavalue":{"value":{"amount":"+0.8435205221176147","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":"Q810053$EF8B7C84-3606-4B52-AC79-E5F6C094E303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca0909599598bea371e3e4cf0a2f553ab00db877","datavalue":{"value":{"entity-type":"item","numeric-id":4302277,"id":"Q4302277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f3caac4be78cea47fe585fbb0089fef8b30fd0c","datavalue":{"value":{"amount":"+0.8233542442321777","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":"Q810053$620D1B37-21DD-4356-ADBD-99424930AB1D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:810053","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:810053"}}}}}