The parameterized complexity of some minimum label problems

DOI10.1016/j.jcss.2010.02.012zbMath1214.05150OpenAlexW2095819433WikidataQ57359760 ScholiaQ57359760MaRDI QIDQ1959420

Michael R. Fellows, Jiong Guo, Iyad A. Kanj

Publication date: 7 October 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.02.012

zbMATH Keywords

fixed-parameter tractabilityW-hardnessedge labeled graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

The label cut problem with respect to path length and label frequency ⋮ Complexity and approximation results on the shared transportation problem ⋮ On the rainbow connectivity of graphs: complexity and FPT algorithms ⋮ Secluded connectivity problems ⋮ On the hardness of labeled correlation clustering problem: a parameterized complexity view ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Unnamed Item ⋮ Improved approximation bounds for the minimum constraint removal problem ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs ⋮ Algorithms and complexity results for labeled correlation clustering problem ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ Maximum cuts in edge-colored graphs ⋮ Generalized rainbow connectivity of graphs ⋮ Refined parameterizations for computing colored cuts in edge-colored graphs ⋮ Colored cut games ⋮ Minimum Cell Connection in Line Segment Arrangements ⋮ Finding disjoint paths in networks with star shared risk link groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms
• On the parameterized complexity of multiple-interval graph problems
• On problems without polynomial kernels
• The labeled perfect matching in bipartite graphs
• Treewidth. Computations and approximations
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Local search for the minimum label spanning tree problem with bounded color classes.
• A note on the minimum label spanning tree.
• Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem
• Approximation algorithms and hardness results for labeled connectivity problems
• Approximation and Hardness Results for Label Cut and Related Problems
• Spanning trees with many or few colors in edge-colored graphs