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
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
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?)
- Max flows in \(O(nm)\) time, or better
- 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
- Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
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
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)
