On the complexity of rainbow spanning forest problem

DOI10.1007/S11590-017-1161-6MaRDI QIDQ1749772zbMATH OpenOpenAlexFDO

Authors Francesco Carrabs, C. Cerrone, Raffaele Cerulli, Selene Silvestri

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 algorithmedge-colored graphgraph theoryrainbow components

Mathematics Subject Classification ID

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

Recommendations

• The rainbow spanning forest problem
• Two heuristics for the rainbow spanning forest problem
• Spanning trees with many or few colors in edge-colored graphs
• Complexity results for rainbow matchings
• On the complexity of packing rainbow spanning trees

Cites work

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

Cited in

(6)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1749772)