On the complexity of the flow coloring problem

DOI10.1016/j.dam.2015.06.025zbMath1321.05075OpenAlexW759230654MaRDI QIDQ499367

Cristiana Huiban, Carlos Diego Rodrigues, Manoel B. Campêlo, Rudini Menezes Sampaio

Publication date: 30 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.06.025

zbMATH Keywords

bipartite graphsNP-hardnessinapproximabilityflow coloringround weighting problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Flows in graphs (05C21)

Related Items

Round weighting problem and gathering in radio networks with symmetrical interference ⋮ Using the minimum maximum flow degree to approximate the flow coloring problem ⋮ A strongly polynomial algorithm for the minimum maximum flow degree problem ⋮ Preface

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong equitable vertex 2-arboricity of complete bipartite and tripartite graphs
• A note on the strong chromatic index of bipartite graphs
• On the complexity of bandwidth allocation in radio networks
• On the computational complexity of strong edge coloring
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Solving the 2-disjoint paths problem in nearly linear time
• Strong edge-colouring and induced matchings
• Algorithms for finding distance-edge-colorings of graphs
• Max flows in O(nm) time, or better