On the complexity of the flow coloring problem

DOI10.1016/J.DAM.2015.06.025zbMATH Open1321.05075OpenAlexW759230654MaRDI QIDQ499367FDOQ499367

Authors Cristiana Huiban, Carlos Diego Rodrigues, Manoel Campêlo, Rudini M. 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

inapproximabilityNP-hardnessbipartite graphsflow coloringround weighting problem

Mathematics Subject Classification ID

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

Recommendations

• The complexity of colouring problems on dense graphs
• The complexity of some graph colouring problems
• scientific article; zbMATH DE number 3913673
• On the Complexity of Ordered Colorings
• On the complexity of H-coloring
• scientific article; zbMATH DE number 4008418
• The complexity of the partition coloring problem
• On the complexity of \(k\)-rainbow cycle colouring problems

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A note on the strong chromatic index of bipartite graphs
• A polynomial time algorithm for strong edge coloring of partial \(k\)-trees
• Algorithms for finding distance-edge-colorings of graphs
• Max flows in \(O(nm)\) time, or better
• On the complexity of bandwidth allocation in radio networks
• On the computational complexity of strong edge coloring
• Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
• Solving the 2-disjoint paths problem in nearly linear time
• Strong edge-colouring and induced matchings

Cited in

(6)

• A strongly polynomial algorithm for the minimum maximum flow degree problem
• Complexity of a classical flow restoration problem
• Round weighting problem and gathering in radio networks with symmetrical interference
• On the parity of colourings and flows
• Using the minimum maximum flow degree to approximate the flow coloring problem
• Preface

This page was built for publication: On the complexity of the flow coloring problem

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