{"entities":{"Q1853178":{"pageid":1863920,"ns":120,"title":"Item:Q1853178","lastrevid":71501595,"modified":"2026-04-13T22:41:01Z","type":"item","id":"Q1853178","labels":{"en":{"language":"en","value":"Parametric analysis of overall min-cuts and applications in undirected networks."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856507"}},"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":"Q1853178$3FB6E8F2-C974-4DA0-8EC9-2F1597BE88F4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0040578ddaf563aa3c98f23551dae0eb8b79db3c","datavalue":{"value":{"text":"Parametric analysis of overall min-cuts and applications in undirected networks.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853178$F2A1B8A1-CAE6-4530-9B65-6A5B98491154","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"102eb43d072b035b5aecb8535077ae6d015b9004","datavalue":{"value":"1042.68002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853178$D68F0C02-D33F-411B-B473-57AE6C89BE05","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"360ceb47bf17049731b6a04f9d15b849e7aa4c7e","datavalue":{"value":"10.1016/S0020-0190(02)00364-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853178$423854D1-7827-439C-A65E-F4A60E0AC77A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"555623c5019e69c450d253a0676460a648d0cb3b","datavalue":{"value":{"entity-type":"item","numeric-id":584055,"id":"Q584055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$342B58BD-48F7-4CD7-9C7F-A482835603CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"044bf92835ff6a19c8d1ac74b6a3bb363b537ee4","datavalue":{"value":{"entity-type":"item","numeric-id":231004,"id":"Q231004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$8BDEF518-7108-4649-889F-C8640A588551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa967b1ef73e5fb3dee34dd7a7344b82ce3e259e","datavalue":{"value":{"entity-type":"item","numeric-id":627449,"id":"Q627449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$68AC58D5-9BC5-413D-BFEA-357FE4F7813F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$4ED96E27-AB3B-46EF-9481-F03C217886BF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853178$9AC5396A-5591-4B7D-859B-AFF872EEE264","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d0d11281def62d45d9f7af018463be4f0643dcdb","datavalue":{"value":"The overall min-cut problem in a capacitated undirected network is well known. Recently Stoer and Wagner gave an elegant algorithm for finding such a cut. In this paper we present a parametric analysis of such a cut where the capacity of an arc \\({i,j}\\) in the network is given by \\(\\min{b_{ij},\\lambda}\\), where \\(\\lambda\\) is a parameter ranging from \\(0\\) to \\(\\infty\\). Letting function \\(v(\\lambda)\\) denote the min-cut capacity, we develop an algorithm to describe \\(v(\\lambda)\\) which involves at most \\(n\\) applications of Stoer and Wagner scheme, where \\(n\\) denotes the number of nodes in the network. We use \\(v(\\lambda)\\) to determine an overall min-cut for multiroute flows as defined by Kishimoto. Such multi-route flows have interesting applications in communication networks.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853178$EBA4849F-D420-4DCD-950F-2BB9E062B514","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca8c16691e9ec83d46a3995338b09d48ac9660ac","datavalue":{"value":"68M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853178$BA56EDD5-F9FA-4651-8DB2-C03EB9191246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853178$9848E36A-64DE-46D2-9F12-77DB8AF7DF56","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac8609f0e3bab6d1bcfe0e8ddcc0b17f56e35157","datavalue":{"value":"1856507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853178$ED759DE1-D987-4DE6-AC18-0F3051609888","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7df51d8ee958129fb1ac1802a0c454ccfc59ce1e","datavalue":{"value":"Graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853178$59EB9CEF-8AE7-4790-B1D5-07BA9B7A03F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"70016a06fa2342dd14c6190533996fb2c9a8718d","datavalue":{"value":"Overall min-cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853178$BA45C681-3140-45F2-88EF-04A67B20FD6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6fd501bec1e4c351a5bb7e183c0156e01d1981e2","datavalue":{"value":"Combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853178$7021C4FC-04B5-49FE-929B-2B4B4A80A3E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1946841ab028237c23d74bdaea35ed522802bb1","datavalue":{"value":"Multiroute flows","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853178$9DA2DA1F-B6EF-4B2A-8282-772820149625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9a45889046ceb36a3929b577590a65659ec360b","datavalue":{"value":"Residual flows","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853178$09B7AF87-A576-4738-BF42-B709843268F8","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":"Q1853178$50D7EA9B-8498-4817-BE47-F0B31C507672","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$9C59ACF0-E237-4162-A867-8D3E020D017F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b789ec3f815a2b7ec523c80c03cc4082a8c2f237","datavalue":{"value":{"entity-type":"item","numeric-id":4537607,"id":"Q4537607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$94B2431F-2A84-4A3B-ACFD-20A2253678BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"434abf09aa6a6718f93d2206368edb9194f711f6","datavalue":{"value":{"entity-type":"item","numeric-id":1811086,"id":"Q1811086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$9F9AA125-C794-4FEB-8C04-523F27697071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a7ef877fc1f04c4ca02dfb519d959f8e1260de1","datavalue":{"value":{"entity-type":"item","numeric-id":4143188,"id":"Q4143188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$E1F228F9-FA68-41D1-907A-FE98C6C2BDD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0efb8a94e57008ad98677311cf447b57ecc0f2cb","datavalue":{"value":{"entity-type":"item","numeric-id":4729349,"id":"Q4729349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$0545051B-3B87-4089-8B56-C3941B38E8D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f13af74c3c96a016096198a2fe0919dca529a5d","datavalue":{"value":{"entity-type":"item","numeric-id":5689762,"id":"Q5689762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$EFBC201E-1A74-47EE-9E04-DA143120FC7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"902615c3c785c5b3550558b02cdca2d453d856ef","datavalue":{"value":{"entity-type":"item","numeric-id":4228440,"id":"Q4228440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$38E42777-CAB6-45F1-A3F1-743AA813664B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f84987f8d99e2687c6f6c7c2c8dbcea6e278915f","datavalue":{"value":{"entity-type":"item","numeric-id":4377588,"id":"Q4377588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853178$AFD51E7F-E7A7-463F-842D-4E39090E2D91","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"801240c4427c59f1fe32c3a5c59bd5dc9e711f59","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00364-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853178$A22BFA24-94F3-48DB-AC7A-9FBA12ADDEF3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc7565e6c55eea601ad074a9d274f8767b0fcd9c","datavalue":{"value":"W2076192504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853178$0B0DEDC6-146F-4100-8BBB-D8BBCCBAAF75","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2d7d9a76c35a030978a397db17b78617d174093","datavalue":{"value":{"entity-type":"item","numeric-id":1811086,"id":"Q1811086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1d0b865cd3965c05ff87e99678c1b85cbfaf7b9","datavalue":{"value":{"amount":"+0.8798579573631287","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":"Q1853178$130F7591-4A14-45AC-A547-A991F4736910","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":"c3c0ad79094a1937f525ba0a07b2229798f2c577","datavalue":{"value":{"amount":"+0.849193274974823","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":"Q1853178$E68AD14D-2603-4CB5-86E4-D31F5D0CE548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d05b3e241a5707468510b2ddd8bc58f83c4930ca","datavalue":{"value":{"entity-type":"item","numeric-id":2465934,"id":"Q2465934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc0f2ae819f16a75cb898e597dda3a0a6adfb6fd","datavalue":{"value":{"amount":"+0.8459860682487488","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":"Q1853178$2C3F68D4-B571-4978-98F3-517806747DB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b0a169badaae943d2647d4571bfe10b8580f9ce","datavalue":{"value":{"entity-type":"item","numeric-id":1186785,"id":"Q1186785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9b35a481aca8057e7b38daf0958cda507209166","datavalue":{"value":{"amount":"+0.8236761689186096","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":"Q1853178$2DA686E8-F789-4BB2-8EA0-650ED7E06AEB","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":"d764b972e878686ebfe1d1ce60574afecd310c55","datavalue":{"value":{"amount":"+0.8115990161895752","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":"Q1853178$95EB6098-E007-487B-B0D9-00A95BB97B49","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parametric analysis of overall min-cuts and applications in undirected networks.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parametric_analysis_of_overall_min-cuts_and_applications_in_undirected_networks."}}}}}