The color-balanced spanning tree problem.

MaRDI QIDQ5389837zbMATH OpenFDO

Authors Štefan Berežný, Vladimír Lacko

Publication date 23 April 2012

Full work available at URL https://eudml.org/doc/33771, http://www.kybernetika.cz/content/2005/4/539

zbMATH Keywords

edge partitionmatroidsNP-completenesspolynomial algorithmsspanning tree

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27)

Recommendations

• Spanning trees with many or few colors in edge-colored graphs
• Contractors' minimum spanning tree
• Balanced problems on graphs with categorization of edges
• The rainbow spanning forest problem
• Uniform coloring of trees

Cites work

• Balanced problems on graphs with categorization of edges
• Categorized bottleneck-minisum path problems on networks
• Color constrained combinatorial optimization problems
• Combinatorial optimization. Networks and matroids
• scientific article; zbMATH DE number 1277120 (Why is no real title available?)
• scientific article; zbMATH DE number 1786153 (Why is no real title available?)
• Minimum perfect bipartite matchings and spanning trees under categorization
• Traveling salesman problem under categorization

Cited in

(14)

• Exact algorithms for the equitable traveling salesman problem
• The robust coloring problem.
• The quadratic balanced optimization problem
• On the weak robustness of interval fuzzy matrices
• The robustness of interval matrices in max-plus algebra
• Average distance in colored graphs
• Looking for edge-equitable spanning trees
• Uniform coloring of trees
• On the Red/Blue Spanning Tree Problem
• The weak robustness of interval matrices in max-plus algebra
• Spanning trees with many or few colors in edge-colored graphs
• Balanced problems on graphs with categorization of edges
• Contractors' minimum spanning tree
• The balanced traveling salesman problem

This page was built for publication: The color-balanced spanning tree problem.

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