{"entities":{"Q378108":{"pageid":379875,"ns":120,"title":"Item:Q378108","lastrevid":61383906,"modified":"2026-04-10T23:01:30Z","type":"item","id":"Q378108","labels":{"en":{"language":"en","value":"On the diameter of partition polytopes and vertex-disjoint cycle cover"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6225207"}},"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":"Q378108$1E1C61F4-AD0B-4558-90AF-48A00A814BE2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"22f7da59f154438daa97a3fbabda6d455d46f345","datavalue":{"value":{"text":"On the diameter of partition polytopes and vertex-disjoint cycle cover","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q378108$ECEB6000-3506-4C9B-AA42-FDA475F8F7E3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c65feb8643318effdf50971df00d63367562c2a","datavalue":{"value":"1288.90049","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$37B2786B-73E7-46D5-ACC4-2789462018F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9882bca72d6da085b9c1905482fbeeea92b521c5","datavalue":{"value":{"entity-type":"item","numeric-id":312671,"id":"Q312671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$63F74695-3DAC-4EB0-94C9-EE8077DAE22C","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":"Q378108$15C470F7-EBEB-46D6-936B-580A6BBFF8F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9da4a2887762bfc0135842b48e115e887ee73eaa","datavalue":{"value":{"time":"+2013-11-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q378108$5C43A402-C9EB-4B13-982B-8092FAF1687D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"70c8399b921bdd99f8365f3c00af891af86ecf0d","datavalue":{"value":"The author gives three bounds on the combinatorial diameter of partition polytopes, a special class of transportation polytopes. They are associated to partitions of a set \\(X=\\left\\{ x_{1}.\\dots ,x_{n}\\right\\} \\) of items into \\(k\\) clusters \\(C_{1},\\dots ,C_{k}\\) of prescribed sizes \\(k_{1}\\geq \\dots \\geq k_{k}.\\) \\noindent The author derives upper bounds on the diameter in the form of \\( k_{1}+k_{2},n-k_{1}\\,\\;\\)and \\(\\left[ \\frac{n}{2}\\right] .\\) Also, he gives exact diameters for partition polytopes with \\(k=2\\) or \\(k=3\\) and prove that, for all \\(k\\geq 4\\) and all \\(k_{1},k_{2}\\), there are cluster sizes \\( k_{3},\\dots ,k_{k}\\) such that the diameter of the corresponding partition polytope is at least \\(\\left[ \\frac{4}{3}k_{2}\\right] \\). Finally, the author provides an \\(O\\left( n\\left( k_{1}+k_{2}\\left( \\sqrt{k}-1\\right) \\right) \\right) \\) algorithm for an edge-walk connecting two given vertices of a partition polytope.","type":"string"},"datatype":"string"},"type":"statement","id":"Q378108$DDAD2320-1CD8-4206-B385-117A2E0582A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"63b70ec5cb69f5c5c9550409918141ca28bfae61","datavalue":{"value":"90C08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$7E3DF09E-40B8-4BA8-BD93-5E8E939C4CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$7DFB233F-CF3D-4416-A5FB-6A399E6B2366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$0B15BACA-C275-4D2A-BF5D-41CE67E74979","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d1642b37301f6bbb016cf74323129e22b78f8da","datavalue":{"value":"6225207","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$E9DADC2F-02CB-4FB2-AE2F-D81699C98E7D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c81d8e6c336dc9f611cde442691714851bfcf830","datavalue":{"value":"transportation polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q378108$AB7E12C9-B302-4F5D-9CD6-6A8E5C4639F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q378108$50811E37-E976-4AF9-920A-5BC45744132E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae446b5111449a4ff62012da77c518047b5997ea","datavalue":{"value":"mathematical programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q378108$86619688-2076-4078-84F1-6B02D9313352","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e168e22a8759ba673c39534d41b1e2b72bc7872e","datavalue":{"value":{"entity-type":"item","numeric-id":488633,"id":"Q488633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$0E5A2A8E-3414-4D61-ABAC-C5062BCD3B89","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":"Q378108$B42F4038-6047-4F4E-A264-9C7E602E0049","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"090b5ed6416d41fb84cc6a8a9827decb45c03751","datavalue":{"value":"https://doi.org/10.1007/s10107-011-0504-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q378108$8F0E83B9-7543-4310-AB4D-E57890E28933","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bae9c9ebb87857f830689371963e28e35b9e933d","datavalue":{"value":"W2037285412","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$64CA8B11-8EF1-4D7F-AC9E-1048F8C8B785","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2beb6dda69e6e7dab003aab2088007d9f0da7ba7","datavalue":{"value":{"entity-type":"item","numeric-id":5576685,"id":"Q5576685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$1C38E456-C798-4ABE-BA66-86D9DDE6FA44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5081ee8e178f8f8cb4d75a6b30102cc3fc422c","datavalue":{"value":{"entity-type":"item","numeric-id":3673577,"id":"Q3673577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$45C77BBD-73AE-4400-B11A-1A01DF8341DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50f8da423a3d4572a2e8e11db86882e78b891d67","datavalue":{"value":{"entity-type":"item","numeric-id":1040845,"id":"Q1040845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$2C3A34B0-2016-4969-874C-C7BACAEE88E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d43328b96eed67798b1e81f01e1a102945a7b385","datavalue":{"value":{"entity-type":"item","numeric-id":4805222,"id":"Q4805222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$F197EB22-8747-4FAF-A6B6-73CABE004B38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a3e04fc5f30d419b5df69c020a296d27e8930dc","datavalue":{"value":{"entity-type":"item","numeric-id":1825756,"id":"Q1825756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$65FA1E7C-FAC2-41E1-BACD-F513FF5D9ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc94950a34505dc52a3f95e757563573b4a41700","datavalue":{"value":{"entity-type":"item","numeric-id":1842660,"id":"Q1842660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$EAF11938-F51D-4908-981F-13D957D24149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7527cd5dfab4f02afaeb6399181c37e2bb0b934","datavalue":{"value":{"entity-type":"item","numeric-id":3212942,"id":"Q3212942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$E462E9C2-3503-477C-9048-1AF056DE9EC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca9945d56e04cd274a3e2533b7d542fac3be86fd","datavalue":{"value":{"entity-type":"item","numeric-id":3374865,"id":"Q3374865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$7E0B8F4D-BDBE-480A-AC03-175663007B29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b594d561d5093acd0001b28f21b65a4fffcd11f","datavalue":{"value":{"entity-type":"item","numeric-id":855825,"id":"Q855825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$02E98D02-1D06-43A8-8839-DA8374A769AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"854bf29386092635a477e0881f3f0c76f5ed2664","datavalue":{"value":{"entity-type":"item","numeric-id":5624995,"id":"Q5624995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q378108$10A6F31B-AE5F-47D2-A084-B77458299EBE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e4d9499833bcab8b9e5d4a2051527425ee5d1fd","datavalue":{"value":"10.1007/S10107-011-0504-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q378108$70E3F9CD-5730-4DC4-82E2-5FE418E01EC7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8bd4bb3005b01d5294c4a0a6206f581c224137d","datavalue":{"value":{"entity-type":"item","numeric-id":4644426,"id":"Q4644426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"462b6ee4dc12a28f80c31a74a4aa9a7db4915eda","datavalue":{"value":{"amount":"+0.7896382212638855","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":"Q378108$06ED3CF2-BDEE-4D36-B490-D0DBF9519FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6121e42cbb516a6d6bd97c907ee2db49285626a0","datavalue":{"value":{"entity-type":"item","numeric-id":271649,"id":"Q271649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5888fd2123f4b218884dd5e6e18bb90d8e3d854","datavalue":{"value":{"amount":"+0.7838374376296997","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":"Q378108$70968E97-1D91-4F52-9EF0-8144140B3A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f9fd972e8b66f5ec38cc11f235771d039693412","datavalue":{"value":{"entity-type":"item","numeric-id":4309970,"id":"Q4309970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d43d32ea166efb6c5027bb259fb9c093dacbf5","datavalue":{"value":{"amount":"+0.7774885296821594","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":"Q378108$B9E6367B-38A5-46D9-8296-5A3F5396C2FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"734f62d2547ebf838087089b8f577342c361c58e","datavalue":{"value":{"entity-type":"item","numeric-id":3991025,"id":"Q3991025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"37d43d32ea166efb6c5027bb259fb9c093dacbf5","datavalue":{"value":{"amount":"+0.7774885296821594","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":"Q378108$CF66856E-01A4-4B05-A7C8-0563DF25595F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d4610cbae3fb684c964be3540bb349a39a0efbf","datavalue":{"value":{"entity-type":"item","numeric-id":3453568,"id":"Q3453568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab237622a765dd2b888078083f2b024ecae41c86","datavalue":{"value":{"amount":"+0.777384877204895","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":"Q378108$0813AB0A-8E82-47CC-AA57-372441E23DB4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the diameter of partition polytopes and vertex-disjoint cycle cover","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_diameter_of_partition_polytopes_and_vertex-disjoint_cycle_cover"}}}}}