The minimum labeling spanning trees
From MaRDI portal
Publication:1567492
DOI10.1016/S0020-0190(97)00127-0zbMath0938.90063OpenAlexW2048177396WikidataQ56077967 ScholiaQ56077967MaRDI QIDQ1567492
Ruay-Shiung Chang, Shing-Jiuan Leu
Publication date: 20 June 2000
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00127-0
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Comparison of metaheuristics for the k‐labeled spanning forest problem ⋮ Greedy approximation for the minimum connected dominating set with labeling ⋮ Worst-case behavior of the MVCA heuristic for the minimum labeling spanning tree problem ⋮ Variable neighbourhood search for the \(k\)-labelled spanning forest problem ⋮ The label cut problem with respect to path length and label frequency ⋮ Solving a \(k\)-node minimum label spanning arborescence problem to compress fingerprint templates ⋮ Least and most colored bases ⋮ Carousel greedy: a generalized greedy algorithm with applications in optimization ⋮ On the bicriterion - minimal cost/minimal label - spanning tree problem ⋮ Bicriteria path problem minimizing the cost and minimizing the number of labels ⋮ The rainbow Steiner tree problem ⋮ Finding minimum label spanning trees using cross‐entropy method ⋮ Biobjective optimization problems on matroids with binary costs ⋮ The Complexity of Bottleneck Labeled Graph Problems ⋮ Approximation algorithms and hardness results for labeled connectivity problems ⋮ Approximation and hardness results for label cut and related problems ⋮ Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem ⋮ Labeled traveling salesman problems: complexity and approximation ⋮ The parameterized complexity of some minimum label problems ⋮ Minimum label \(s\)-\(t\) cut has large integrality gaps ⋮ Computational complexity analysis of the sensor location flow observability problem ⋮ Solving the minimum label spanning tree problem by mathematical programming techniques ⋮ On the complexity of rainbow spanning forest problem ⋮ The complexity for partitioning graphs by monochromatic trees, cycles and paths ⋮ A hybrid metaheuristic for the minimum labeling spanning tree problem ⋮ Multicriteria path and tree problems: discussion on exact algorithms and applications ⋮ Discrete particle swarm optimization for the minimum labelling Steiner tree problem ⋮ Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems ⋮ Variable neighbourhood search for the minimum labelling Steiner tree problem ⋮ Reload cost problems: Minimum diameter spanning tree ⋮ A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants ⋮ Algorithms and complexity for a class of combinatorial optimization problems with labelling ⋮ The complexity of bottleneck labeled graph problems ⋮ OMEGA one multi ethnic genetic approach ⋮ The labeled maximum matching problem ⋮ The rainbow spanning forest problem ⋮ Monochromatic and heterochromatic subgraphs in edge-colored graphs - A survey ⋮ Local search for the minimum label spanning tree problem with bounded color classes. ⋮ A mixed integer linear formulation for the minimum label spanning tree problem ⋮ Greedy randomized adaptive search and variable neighbourhood search for the minimum labelling spanning tree problem ⋮ On the minimum label spanning tree problem ⋮ Solving the minimum labelling spanning tree problem using hybrid local search ⋮ The labeled perfect matching in bipartite graphs ⋮ A polyhedral approach to the generalized minimum labeling spanning tree problem ⋮ A note on the minimum label spanning tree. ⋮ Heuristic approaches for the Minimum Labelling Hamiltonian Cycle Problem
Cites Work