{"entities":{"Q1186785":{"pageid":1197534,"ns":120,"title":"Item:Q1186785","lastrevid":69848109,"modified":"2026-04-13T10:45:00Z","type":"item","id":"Q1186785","labels":{"en":{"language":"en","value":"A fast algorithm for the generalized parametric minimum cut problem and applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 37160"}},"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":"Q1186785$A36D676D-F37B-4821-8C9B-FF89D105FD6C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fbc96c4a1e6b74ccf595113e882bad3e9e960b07","datavalue":{"value":{"text":"A fast algorithm for the generalized parametric minimum cut problem and applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1186785$F0ECE4CA-9C10-49EF-8FDB-D06CB8969652","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"467207e5d69bdea5f75c4d04a464778999fe9453","datavalue":{"value":"0763.90081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$CF21AA58-C79D-4394-BDD8-FEAEFEB9E0EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"005c6ecab6e5d46df1810f6aea39fc23c2a9f223","datavalue":{"value":"10.1007/BF01758775","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$523B415E-0A7E-4830-A02F-2D471AC9E1C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e43ec2b202e198d6095e3eb7d39c15e272952dda","datavalue":{"value":{"entity-type":"item","numeric-id":793742,"id":"Q793742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$F254D2A3-7D37-45EA-BDCF-898D4D06820D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"855d8872a495aa24469c23359eec4865d90d55e0","datavalue":{"value":{"entity-type":"item","numeric-id":1062625,"id":"Q1062625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$0604D7DB-3C3D-4EAC-99C0-79298505F90D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$AF08C979-1483-4980-8D79-05F6EB31F76F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-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":"Q1186785$97ED0434-A398-4315-B6A3-F37C5E095C3E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"74057574253a67e7cf9e921520089c18cb8fe974","datavalue":{"value":"Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter \\(\\lambda\\). Recently Gallo et al. showed that for an important class of networks, called monotone parametric flow networks, a sequence of \\(O(n)\\) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the \\(\\lambda\\) values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of \\(\\lambda\\). This paper shows how to remove both of these assumptions while obtaining the same running times.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186785$F4D76824-5AA0-4240-8134-5D2C11B4A8D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$FEB0CD43-F16F-4DC7-82A5-1D11CEEB5D4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$F4BA13C6-7676-4394-8212-B675C159AB7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$1B413FBC-1146-4D04-9556-042C10ED6E9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$D0DF2010-CFC9-4530-A15F-2A63B7A14999","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9c4deba1681b8e282afba6ecd91e8823ab4e4e25","datavalue":{"value":"37160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1186785$59124931-79BD-40B4-AB66-2E9E3C000F9D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91e2d4185ebd3e822e1265b08ad72282a4bdc7b4","datavalue":{"value":"parametric minimum cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186785$2CD80B11-FB83-47BA-8E31-C5DCD2F36E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1963d0d9064e4a48c264c5d861cc3a4dcae86b2c","datavalue":{"value":"sequence of network flow computations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186785$8B14C5F8-A9EE-4B59-B6E3-4965308C7E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93054e70f0a8090bdbda34801834e8b4e85c034c","datavalue":{"value":"monotone parametric flow networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1186785$62C0F992-28D2-4474-A446-C0BFF4BE3C25","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":"Q1186785$A580B9E0-7EC8-4C74-B174-6E5D91BA5BA2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d9754a6691c24f2be00e76de234846041c6d065","datavalue":{"value":{"entity-type":"item","numeric-id":4099196,"id":"Q4099196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$90DF0D8C-A06F-4E60-B724-25012AC3FAF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3544ff5c3325f5ac1e5dcd2fd92020bf1b6189fb","datavalue":{"value":{"entity-type":"item","numeric-id":3292914,"id":"Q3292914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$5B105A05-29E5-4F1A-938C-97B35AD0D99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd41a3d3ffce78a856861213ff6553c14d782cc0","datavalue":{"value":{"entity-type":"item","numeric-id":5904119,"id":"Q5904119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$331E761C-6831-411D-87E4-72F16EF04FE4","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":"Q1186785$4B8F2DEA-34F5-46F9-BC9A-55118464C1D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79f7f06ae9524634bd51bd90fd496fbe88810422","datavalue":{"value":{"entity-type":"item","numeric-id":3995616,"id":"Q3995616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$0766D97B-AE4A-48C4-9DCE-49FA4F395FD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0596aa5a031787403ec4e7d6182870b0312e0feb","datavalue":{"value":{"entity-type":"item","numeric-id":5639561,"id":"Q5639561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$E96A519C-A311-4FD9-8044-F5B2C74BCE41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0faa1a33ff4a89c58db45e03eb3ff50ee29a9e6c","datavalue":{"value":{"entity-type":"item","numeric-id":3751000,"id":"Q3751000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$1A5AAF5E-EEA7-4E20-AE4A-B4AF8EAB561A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92fa191d3fd93af0064a83ecf8434b6e5b925636","datavalue":{"value":{"entity-type":"item","numeric-id":4130997,"id":"Q4130997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$ECFE0D70-AF10-4946-AC0C-45DD2228B1CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$321E26CA-C894-46B1-A0C3-FA315C5324FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f2c062229b6e77da50c0b4a84e0c164d7e511a8","datavalue":{"value":{"entity-type":"item","numeric-id":4161098,"id":"Q4161098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$24A9AA1F-1886-469D-BAE4-41CEF336D7ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd5291d4aaf0fe56994abe4132f5cb7c329d4895","datavalue":{"value":{"entity-type":"item","numeric-id":3768905,"id":"Q3768905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$C3742574-23E1-41BA-9C7F-ED4D340641A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e7be97aafd07489aa3924bcaed5ff77555d8e36","datavalue":{"value":{"entity-type":"item","numeric-id":5524214,"id":"Q5524214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$FDDADD96-F5B3-4464-A7F4-0BB7EA650AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454356a2a554783d10b0a04e8f10e67691ded68d","datavalue":{"value":{"entity-type":"item","numeric-id":4158484,"id":"Q4158484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$6939B94B-022D-41F8-8A69-A9D2594309B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc6e689ca9104617943bd76b284824e0c9ceb6bd","datavalue":{"value":{"entity-type":"item","numeric-id":3707420,"id":"Q3707420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$853BB9AB-FFAB-42EA-9D81-77A81C342DAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80f4ab2174f329549e800b824393134a7fb501db","datavalue":{"value":{"entity-type":"item","numeric-id":3877380,"id":"Q3877380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1186785$770A0787-64F7-44C9-915C-343D25E18640","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18777196c73089a9862c15ac78185d81a766e2fb","datavalue":{"value":{"entity-type":"item","numeric-id":4729349,"id":"Q4729349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d3a55a32d6729ca7478d7ec5a9c67e7087bb936","datavalue":{"value":{"amount":"+0.8984035849571228","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":"Q1186785$77607818-41EE-46FF-B7BA-08CB6F6F93C9","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":"6f38ee8e8d713addf43dc595d915a16eae1285b3","datavalue":{"value":{"amount":"+0.855290949344635","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":"Q1186785$85A999A5-D619-49F9-BE63-606E6F925E43","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":"8810d9e38a6c4b638a8e4475008b56a952ff8ad0","datavalue":{"value":{"amount":"+0.8445889353752136","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":"Q1186785$2CE54C27-E47A-4699-AA4A-9FD4CCBE8FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56d6b0062da7d0713e0446870fbe2b584d1075eb","datavalue":{"value":{"entity-type":"item","numeric-id":4649339,"id":"Q4649339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92c049f5d07c64b006cb137ef973576d3656cf0a","datavalue":{"value":{"amount":"+0.8392792344093323","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":"Q1186785$BA91A04F-AFBA-40F8-882F-FFD0862EB722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce1dfc4687ba1ee56f909725b794187d357b9878","datavalue":{"value":{"entity-type":"item","numeric-id":2480211,"id":"Q2480211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2039226333416c295c5100379494c13f4fe48b43","datavalue":{"value":{"amount":"+0.8359033465385437","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":"Q1186785$99400125-9E97-4ED6-94B3-AD6CE9C469E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A fast algorithm for the generalized parametric minimum cut problem and applications","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_fast_algorithm_for_the_generalized_parametric_minimum_cut_problem_and_applications"}}}}}