{"entities":{"Q5920404":{"pageid":8052713,"ns":120,"title":"Item:Q5920404","lastrevid":50247221,"modified":"2026-01-13T15:40:22Z","type":"item","id":"Q5920404","labels":{"en":{"language":"en","value":"Exact algorithms for a discrete metric labeling problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5225176"}},"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":"Q5920404$825D72C7-E04D-46C0-B03B-E1317AAA53DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f28aa15e71d27b04d88e1f2bc612eef80902815","datavalue":{"value":{"text":"Exact algorithms for a discrete metric labeling problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5920404$EDF9C459-613B-4D7B-9EC3-BE8E9D14090E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"87c734c6f2c013c811db4b22f5be65ff5e06f993","datavalue":{"value":"1130.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$875E38AA-8D49-41C5-9EE0-F499D0BD94F7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1acd013286f115e888ead41c9bce5ca703cfdd89","datavalue":{"value":{"entity-type":"item","numeric-id":499304,"id":"Q499304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$AAA346D0-138D-45C7-97CF-3716A37FC8CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da11008dc05008b1d4057e867f18c9dfae5601a3","datavalue":{"value":{"entity-type":"item","numeric-id":294720,"id":"Q294720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$9A253DDD-1E09-4FBE-8B8B-322C7C418CEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5be63c3960e6be84db93e9bc08ff91802cce759","datavalue":{"value":{"entity-type":"item","numeric-id":325481,"id":"Q325481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$51FD2217-7315-4852-8453-B72FDC3F7F33","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38a7711cbf1baaa0ee796eb33cf4a496b343c914","datavalue":{"value":{"entity-type":"item","numeric-id":408368,"id":"Q408368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$EE597392-7027-4477-97A4-2112CD6E97AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5095aa6ecf8c9ac2c346b3376501c7dadbffcfa0","datavalue":{"value":{"time":"+2008-01-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":"Q5920404$6F40C96D-CAC2-4FC8-AB69-D2C5F036DFE2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4d5959d5f9cb5797b70e4df863705e0276b0d2e8","datavalue":{"value":"Let \\(G=(V,E)\\) be an edge-weighted undirected graph, and \\(C\\) be a finite set of colors. Furthermore for each vertex \\(v\\) a non-empty subset \\(C_v\\) of colors is associated. A vertex coloring \\(\\varphi\\) is feasible if for each \\(v\\) we have \\(\\varphi(v) \\in C_v.\\) To find a feasible coloration which minimizes the total edge weights of the color-changing edges (edges with differently colored vertices) is called discrete metric labeling problem, and was introduced by this paper. This is a special case of the metric labeling problem of J. Kleinberg and E. Tardos (therefore the approximation algorithm of the latter also works on it). The problem is also closely related to the colored multiway cut problem of P. L. Erd\u0151s and L. A. Sz\u00e9kely. Finally the problem provides a mean to deal with flexible manufacturing systems. The main contributions of the paper is the exact solutions of discrete metric labeling problem for trees, cycles and graphs with small tree-width. It also introduces a general branch and bound algorithm to solve the general (NP-hard) problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5920404$0E5ACEE3-04E1-4CBA-95EA-B43B8F8A0D75","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"01b0989d65d3fe37f1a608a8cd96e416bda56c38","datavalue":{"value":{"entity-type":"item","numeric-id":200913,"id":"Q200913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$FB4CDF5D-A230-4C89-9913-519F5A068A9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$EE29FA6C-6BE6-43A0-AED7-2C2B976750C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$31D92C8B-EF54-4876-AB74-C8AF55A6E1D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$8FC978C2-2AE4-402E-B918-3A9B7EF1A0CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$3F0D4D33-5FF1-43D4-898C-C725422258FD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d61588abefab53e27f66223c064cc8d20b7e469e","datavalue":{"value":"5225176","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$1DDD039D-05D5-4D3B-BD32-50B516E91078","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01f6778b7579c5450a8efc3c6ab832a66d83e24a","datavalue":{"value":"multiterminal cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q5920404$729C6EC8-193A-44B8-BAFE-A422507BF2CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68141dd0484467c3e03efa989273155166207dda","datavalue":{"value":"multiway cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q5920404$14B932F0-0813-493A-9B51-11999E2CCB25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b81b0e661ffd7a2b0cf4d74a6388abe874250e20","datavalue":{"value":"tree-width","type":"string"},"datatype":"string"},"type":"statement","id":"Q5920404$247117A1-3D8E-4C88-A91D-303F0E743798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5920404$FC90EACB-4A2E-44C2-875C-BCA5A16F3493","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":"Q5920404$126668B5-5B32-47EC-8B8B-0B252536823C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f773f87f6b35e91243966700ee217591fec7985c","datavalue":{"value":"https://doi.org/10.1016/j.disopt.2006.05.009","type":"string"},"datatype":"url"},"type":"statement","id":"Q5920404$51AF45A2-048E-4136-8250-0F402F63F176","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bb473d87ef5824ba24362a775055231fbc17c659","datavalue":{"value":"W2139116018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$56FA4E4E-BF86-46D7-A7F9-BC112118ECC6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$6DB8F506-C01A-4BCC-9050-E36416E4E6B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$9069D8DB-4852-40AC-9DF5-E78AA471C171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$01E8CE34-D2CC-49DD-81AF-0EEA77891B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c36b42b281969cc247486ad758e619940ccb2d97","datavalue":{"value":{"entity-type":"item","numeric-id":4305362,"id":"Q4305362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$BBB95B29-FD15-4128-A005-7A48744E2562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$DE4613A0-0534-425A-87C4-BFA87C0E26FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d3f2d49423807bb7c97c2760cb6addbc2d22359","datavalue":{"value":{"entity-type":"item","numeric-id":1802347,"id":"Q1802347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$4FF358B9-3D68-45C0-8676-404076DEBDDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"278739ef095d9e984fc96524f080b6f05a9d4f36","datavalue":{"value":{"entity-type":"item","numeric-id":1334954,"id":"Q1334954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$D3DA8781-130B-42A5-93EE-378E8D4B25E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97629a956f437ce60853cad390a73c8c525cdc4e","datavalue":{"value":{"entity-type":"item","numeric-id":3221420,"id":"Q3221420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$A4BA5E5F-0002-4F8B-8AD4-87FF8F7F7059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dca36dcf6c23bc86e9edd764a6485d407dae7eb2","datavalue":{"value":{"entity-type":"item","numeric-id":3455544,"id":"Q3455544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$CB769C5C-5BEB-48F0-85E1-622A8A8EC1CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0baa054aba2e768d8828bbc09207c72ddd444ab2","datavalue":{"value":{"entity-type":"item","numeric-id":5285230,"id":"Q5285230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5920404$A6FE2BF3-472E-4F0C-AB6B-8A3EAA6F8810","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"afc8537cce2422dd1729221fd154bf9e69705a52","datavalue":{"value":"10.1016/J.DISOPT.2006.05.009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5920404$079D9D93-F1A4-4B0A-85CE-0D7A261121BC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40d86888fd80e2ef1b6b3916a3cb411bb45f77c7","datavalue":{"value":{"entity-type":"item","numeric-id":5899363,"id":"Q5899363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3da0a6b20c22f64488f198c4bc4d0f10e0e9299a","datavalue":{"value":{"amount":"+0.9040919542312622","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":"Q5920404$71598B3A-6D74-451C-A63E-0495C7323EC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a15858b27ceaf3f80bd01cfe7859762fd7e60f5","datavalue":{"value":{"entity-type":"item","numeric-id":5422491,"id":"Q5422491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82f55442f8348c40c9a083d1f4725980c5730504","datavalue":{"value":{"amount":"+0.788425087928772","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":"Q5920404$1BA69167-A665-4FCB-BD3E-5C1437FC4B09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a952b6690b0f617f620b9d534c7477afcffb3839","datavalue":{"value":{"entity-type":"item","numeric-id":2768280,"id":"Q2768280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49d904673a3f79b8fd6c2434cd753f170aefa828","datavalue":{"value":{"amount":"+0.7612935900688171","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":"Q5920404$7B745A51-5217-4C5C-8434-39162FDD1A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e445521817344fe115c61ebe5c7309af8bf0076","datavalue":{"value":{"entity-type":"item","numeric-id":3192037,"id":"Q3192037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49d904673a3f79b8fd6c2434cd753f170aefa828","datavalue":{"value":{"amount":"+0.7612935900688171","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":"Q5920404$C3119928-8B35-4AB5-8661-CA120179570F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f47b25208a3c2be518981575bd5659e5abba1b00","datavalue":{"value":{"entity-type":"item","numeric-id":2178329,"id":"Q2178329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cfd86f5136bb9821b73459bd34d477e449da82c","datavalue":{"value":{"amount":"+0.7558372020721436","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":"Q5920404$7D99B4B7-04FC-4FEF-86C2-7DEDDE4D0E89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5920404","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5920404"}}}}}