{"entities":{"Q1116893":{"pageid":1127642,"ns":120,"title":"Item:Q1116893","lastrevid":69681633,"modified":"2026-04-13T08:40:39Z","type":"item","id":"Q1116893","labels":{"en":{"language":"en","value":"A matroid algorithm and its application to the efficient solution of two optimization problems on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4089333"}},"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":"Q1116893$E4C8BF6A-8BFC-4095-8B7F-09C5FF1774A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c5538f025e2f2555c7f880d046f1bbf4424e6b7e","datavalue":{"value":{"text":"A matroid algorithm and its application to the efficient solution of two optimization problems on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116893$0ABAF088-5871-4808-B654-FF3A409D60BD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26aa4c65cbf0c2c7d292e916035af39f86e41064","datavalue":{"value":"0665.90076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$91542DDF-03CC-4146-A75D-0087656C09E7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cdeb87d0632f4cd98940cd30c7635326b8dcf116","datavalue":{"value":"10.1007/BF01589417","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$4C531579-6B05-44B3-86C1-019632138A9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"02f7422aee236690a26f262d5a00c7db9808fb6a","datavalue":{"value":{"entity-type":"item","numeric-id":1116892,"id":"Q1116892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$424D3ECC-A7EC-4BF1-BDD5-C4CD75C63B8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bba0dc06d9e863feee266304b6624ac54f793c4","datavalue":{"value":{"entity-type":"item","numeric-id":168083,"id":"Q168083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$DFDF0052-1DDA-4B63-9A45-E28D084D137F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"feb07495fa8de76912d587852b3aa20404b344f1","datavalue":{"value":{"entity-type":"item","numeric-id":163019,"id":"Q163019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$1D495BEA-420D-4B4E-A065-7673F2767A55","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$D3EF70A8-8E84-4DB0-86E6-1626B20E591C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1116893$33A8A1EC-1F72-4350-A353-5E8EB2CFA9F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d0e540c04b1b24ca0160e05c74fa6a894083fabb","datavalue":{"value":"We address the problem of finding a minimum weight base B of a matroid when, in addition, each element of the matroid is colored with one of m colors and there are upper and lower bound restrictions on the number of elements of B with color i, for \\(i=1,2,...,m\\). This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity \\(O(| E\\| V| +| V|^ 2\\log | V|)\\). Here V denotes the node set of the underlying bipartite graph, and E denotes its edge set. The second application is defined on a general connected graph \\(G=(V,E)\\) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with color i in the tree, for each i. Our algorithm for this problem has complexity \\(O(| E\\| V| +m^ 2| V| +m| V|^ 2)\\). A special case of this constrained spanning tree problem occurs when \\(V^*\\) is a set of pairwise nonadjacent nodes of G. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node of \\(V^*\\). Then the complexity of our algorithm is \\(O(| V\\| E| +| V^*\\| V|^ 2)\\). Finally, we discuss a new relaxation of the traveling salesman problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$8FD30FA3-F5BB-4750-8AEE-389C15169BBB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$39D4C018-1B0D-4F22-83E8-B8C9A437178D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$9FFD8912-D0E6-4A9D-AC0E-422485A6CF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$890FE6F9-68B8-470D-A2EF-24037940D3B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$8B511C30-06F6-4890-9CE4-BA387B68BAB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$0B39532D-8AB8-4FA7-8975-FCCB210305B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"402443e609132401c94e6b1a7f4762e076cff2da","datavalue":{"value":"4089333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116893$7E8ECF8E-CEDA-4869-B3D9-08F238FA396F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"771d937db3cc3e653ec7e55a6c37658d408618a6","datavalue":{"value":"minimum weight base","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$7323DA71-65EA-4484-83BB-236C7775AF4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$EA2224A7-9FED-4026-A2DC-2F3152395694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90c33c2f12b8719fe629f3d999c658f891209d0d","datavalue":{"value":"weighted bipartite matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$DE2831F2-420C-4535-8FA9-BF21C21310D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3065e23cb4d051d6be889edc03bf67315b4d9fcd","datavalue":{"value":"minimum weight spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$395487BC-CF69-4516-8F6E-E94E5EE68DE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e7e77ce1f5fe7a5db9c41439f0d95f94c2e0ad9","datavalue":{"value":"upper and lower bound restrictions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$3D322AE2-EBB5-4CE9-977C-97EF1143DC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0245a4aeb76b9b1dc04bb886490fa5ef546c3af6","datavalue":{"value":"traveling salesman","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116893$7D4DB3AA-8128-445F-BA46-1DF7B90A629B","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":"Q1116893$941011A8-618C-4197-B38B-69FCDFD930F1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3d25a1a5e53297c46a66ca1d4755989c397bf3e","datavalue":{"value":{"entity-type":"item","numeric-id":3770280,"id":"Q3770280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$0A266821-AA1B-4975-AA23-960F3F39F2DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$01A1954D-15B0-444F-B121-EAE94AB0A683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2f1418cda1b0b9a975cd52bf50e78acbd1bc719","datavalue":{"value":{"entity-type":"item","numeric-id":3205244,"id":"Q3205244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$0BA0783A-545B-4BDB-80C1-E94EDD311F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d601b5a73aa3f981ed43e68477a6afb0b2f45837","datavalue":{"value":{"entity-type":"item","numeric-id":1086246,"id":"Q1086246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$2140EC66-57FF-4E83-B04D-AFABDB19261C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9beef10f14c1534c9b646b394bb6806fa6bcf5a6","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$33AB6BE9-61A7-4B51-9D62-5138DDA22030","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17b46f23e1d95210ec444c78dd7a8edd18f2e48d","datavalue":{"value":{"entity-type":"item","numeric-id":1062461,"id":"Q1062461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$72B8995E-0DC4-4961-852C-39C7D649F3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f73eb84a543b338a4a079febb7b97c03a91da92f","datavalue":{"value":{"entity-type":"item","numeric-id":5633847,"id":"Q5633847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$B5C79B14-3D80-4C74-B355-C9C69FF25316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5b903864765fb40a5b80f7f222eabf61ff3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":5641007,"id":"Q5641007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$2595DE5D-C8A0-44C2-9D37-4DB55CE49052","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":"Q1116893$2CC48F33-A18D-43BC-A3E0-7FCD64DE749E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3622614d72b88a9de98c8ab24ffd0a6d7ffd367","datavalue":{"value":{"entity-type":"item","numeric-id":1823163,"id":"Q1823163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$FC2832FD-9ABB-4B43-B41B-21B88A07A670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2926d545828cf2546c04394eed0338b9412faa2","datavalue":{"value":{"entity-type":"item","numeric-id":1218265,"id":"Q1218265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116893$412081C3-CBF8-42A5-A2A0-711D5952B170","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"602284fcd76f40fe042bf377880f6fe0147f2855","datavalue":{"value":{"entity-type":"item","numeric-id":1825757,"id":"Q1825757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb88676482786835da0f1e27deab26f7be148ff1","datavalue":{"value":{"amount":"+0.8580768704414368","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":"Q1116893$3BD4A4DF-D827-4E24-89CF-D5384B0B8D7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d049b2867fc19c693dbf3c93c07edd6cb2817ab","datavalue":{"value":{"entity-type":"item","numeric-id":3823151,"id":"Q3823151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"793ac687809f9b55584c08c398c8c4f1875172da","datavalue":{"value":{"amount":"+0.8521836400032043","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":"Q1116893$28E768D1-B330-4477-A29B-ED7845CC9692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e61ec7d4ece6914eaa7e4b7017b769b27da7f4b7","datavalue":{"value":{"entity-type":"item","numeric-id":3335803,"id":"Q3335803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19b92013599b5763a1d9ddbf86c9cb8e866c2ca2","datavalue":{"value":{"amount":"+0.8367564678192139","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":"Q1116893$6150C5BD-9F93-4A97-8F89-70451586601D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f03120bbe5633b4a00709916f411612736861ca8","datavalue":{"value":{"entity-type":"item","numeric-id":4724652,"id":"Q4724652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab6347944d263fc5f2841b5fe0373dbd05c88ac5","datavalue":{"value":{"amount":"+0.821260929107666","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":"Q1116893$16543C5B-AADA-4256-A38D-DEC3E5623E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a28c9a2d577fc104a706984364e831f3937ef9ec","datavalue":{"value":{"entity-type":"item","numeric-id":3682487,"id":"Q3682487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"561448c096365bd3c32aa6e13d0693aa2076d410","datavalue":{"value":{"amount":"+0.8206589818000793","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":"Q1116893$9133B25D-B146-4E57-A09A-1D6883C58F3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A matroid algorithm and its application to the efficient solution of two optimization problems on graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_matroid_algorithm_and_its_application_to_the_efficient_solution_of_two_optimization_problems_on_graphs"}}}}}