{"entities":{"Q1297737":{"pageid":1308487,"ns":120,"title":"Item:Q1297737","lastrevid":67314402,"modified":"2026-04-12T16:47:55Z","type":"item","id":"Q1297737","labels":{"en":{"language":"en","value":"A combinatorial algorithm for the minimum \\((2,r)\\)-metric problem and some generalizations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1336284"}},"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":"Q1297737$C8CC1BA6-0782-43B5-A404-64886AC58393","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"389a85aba6d912d28d62604a578b6fb484ebae46","datavalue":{"value":{"text":"A combinatorial algorithm for the minimum \\((2,r)\\)-metric problem and some generalizations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1297737$0442BB4D-5921-4D1A-9FF3-F9A84274B70A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d3fdc5b8a999c8d5eda8d1b06da586c554847f82","datavalue":{"value":"0924.90126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$C2AFD454-6E4B-402A-A7E1-119810B9AD14","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"14fc360ec3034cf7b4974dd2757eb533d1dfaac7","datavalue":{"value":{"entity-type":"item","numeric-id":423889,"id":"Q423889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297737$F504C414-A68E-484E-9751-67A5EFA67F90","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297737$A4E16116-135D-4F7B-96A8-3ECDD9202241","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b4297ec79a5682b9b76f73920b9542007332ff55","datavalue":{"value":{"time":"+1999-09-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1297737$D95862D2-3789-4979-B7F3-119EA3C217EA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe9b3d12c64a4694ddd912ff6f4bcfa35b57d556","datavalue":{"value":"A graph \\(G(V,E)\\) is given with nonnegative integer capacities \\(c(e)\\) on the edges \\(e\\in E\\) and with a metric \\(\\mu\\) establishing distances between pairs of vertices of \\(T\\subseteq V\\). This metric should be extended to a (semi-)metric \\(m\\) on \\(V\\) so that \\(m=\\mu\\) within \\(T\\), each \\(x\\in V\\) is at zero distance from some \\(t\\in T\\), and \\(\\sum_{e\\in E} c(e)m(e)\\) be as small as possible. This is the classical undirected cut problem for \\(T=\\{s,t\\}\\). Another special case is if \\(\\mu\\) is the path metric (minimum number of edges in a path connecting the vertices) in the complete bipartite graph \\(K_{2,r}\\). This latter problem is polynomial but previous solutions used the ellipsoid method. The author gives a ``purely combinatorial'' method for this and for a certain associated integer multiflow problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297737$956E5376-95CD-41E0-8C3E-6A91EC2895DA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1297737$1794744B-279A-4359-A7A9-AFCB3110B150","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$DAF6EFB9-1731-40BD-9F60-13FA1647422A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$419D3956-B64B-4830-90FA-4DA9EF2BB5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$53144C69-5B1F-483C-AFFC-6FB4BF4A5A87","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dfcab4912a38029d472dd715db5ef0f9133fc3f6","datavalue":{"value":"1336284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$929DF4C4-8FB0-4350-AD60-C5FABE2B8BC4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"47091c2744749288ff90b22066760584490294f5","datavalue":{"value":"minimum \\((2,r)\\)-metric problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1297737$1659CC9C-E1B9-4972-AC82-6524CFFA833E","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":"Q1297737$B122260A-5593-4F80-B18A-AEE6AC44369D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82b10b7fbb18875628cbccbfccad11f5bc0fa8f9","datavalue":{"value":"https://doi.org/10.1007/s004930050040","type":"string"},"datatype":"url"},"type":"statement","id":"Q1297737$6BC0BD7F-87D5-4906-B710-0C62C62FE6FA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7a8a4ad6a48c32ef0b09f8e4d7b978d3516466a0","datavalue":{"value":"W2086358569","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$1E069F48-1A41-4420-9BD9-E619B0173809","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfce378392d2fc491aaaa63dde7ff1bf7711a39b","datavalue":{"value":"10.1007/S004930050040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1297737$33A286A5-CEBD-4B97-B402-47993E469DA7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec21872278ce3c2dff860704dffc9e5751c82aa1","datavalue":{"value":{"entity-type":"item","numeric-id":1911842,"id":"Q1911842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0d979580f1a9330160f90aded8dbfadc9030acd","datavalue":{"value":{"amount":"+0.8677828311920166","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":"Q1297737$D0C69A62-AFD7-404B-85AA-7423AE81C542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc933becdb78349bca066365faa49c42a22cb3b6","datavalue":{"value":{"entity-type":"item","numeric-id":3680585,"id":"Q3680585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"803575727ca894feaa66bd7f27700ee0c096a47b","datavalue":{"value":{"amount":"+0.8177463412284851","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":"Q1297737$5430DDC4-AA06-48E0-BEC4-979CCEA015BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4201ab5e06ac0eb1bf3e5ab3ceab62af4a30a22","datavalue":{"value":{"entity-type":"item","numeric-id":1584451,"id":"Q1584451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb4e759ec046ea0e02c957ff6586c2306d18af68","datavalue":{"value":{"amount":"+0.7976142168045044","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":"Q1297737$80F428EA-9F3B-4695-97AF-56BBBD026A1C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A combinatorial algorithm for the minimum \\((2,r)\\)-metric problem and some generalizations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_combinatorial_algorithm_for_the_minimum_%5C((2,r)%5C)-metric_problem_and_some_generalizations"}}}}}