On the complexity of rainbow spanning forest problem

DOI10.1007/s11590-017-1161-6zbMath1400.90256OpenAlexW2664277112MaRDI QIDQ1749772

Carmine Cerrone, Raffaele Cerulli, Selene Silvestri, Francesco Carrabs

Publication date: 28 May 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-017-1161-6

zbMATH Keywords

approximation algorithmgraph theoryedge-colored graphrainbow components

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (6)

Exact approaches for the orderly colored longest path problem: performance comparison ⋮ The rainbow Steiner tree problem ⋮ Two heuristics for the rainbow spanning forest problem ⋮ On the complexity of rainbow spanning forest problem ⋮ The rainbow spanning forest problem ⋮ An exact reduction technique for the k-colour shortest path problem

Cites Work

• Unnamed Item
• Vehicle-ID sensor location for route flow recognition: models and algorithms
• A branch-and-cut algorithm for the minimum labeling Hamiltonian cycle problem and two variants
• Discrete particle swarm optimization for the minimum labelling Steiner tree problem
• The labeled maximum matching problem
• The minimum labeling spanning trees
• On the minimum label spanning tree problem
• Carousel greedy: a generalized greedy algorithm with applications in optimization
• On the complexity of rainbow spanning forest problem
• Variable neighbourhood search for the minimum labelling Steiner tree problem
• On the minimum monochromatic or multicolored subgraph partition problems
• A necessary and sufficient condition for the existence of a heterochromatic spanning tree in a graph
• The Colorful Traveling Salesman Problem
• Spanning trees with many or few colors in edge-colored graphs
• The Rainbow Cycle Cover Problem
• Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs
• Multicolored forests in complete bipartite graphs
• OMEGA one multi ethnic genetic approach

This page was built for publication: On the complexity of rainbow spanning forest problem