On the complexity of the flow coloring problem

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

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

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)

Cites Work

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

Cited In (6)

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

Recommendations

• The complexity of colouring problems on dense graphs 👍 👎
• On the complexity of H-coloring 👍 👎
• The complexity of some graph colouring problems 👍 👎
• On the complexity of rainbow coloring problems 👍 👎
• The complexity of the partition coloring problem 👍 👎
• On the complexity of \(k\)-rainbow cycle colouring problems 👍 👎
• On the Complexity of Ordered Colorings 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)