Using the minimum maximum flow degree to approximate the flow coloring problem

DOI10.1007/s10479-021-04180-3zbMath1497.05247OpenAlexW3175413318MaRDI QIDQ2675725

Jhonata A. S. Matias, Manoel B. Campêlo

Publication date: 26 September 2022

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-021-04180-3

zbMATH Keywords

approximation algorithmgraph algorithmsnetwork flowflow coloring problemflow degree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Flows in graphs (05C21)

Cites Work

• Unnamed Item
• On the complexity of the flow coloring problem
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• On the complexity of bandwidth allocation in radio networks
• Edge-coloring of multigraphs: Recoloring technique
• A better than “best possible” algorithm to edge color multigraphs
• The NP-Completeness of Edge-Coloring
• Bipartite Edge Coloring in $O(\Delta m)$ Time
• Max flows in O(nm) time, or better
• A Theorem on Coloring the Lines of a Network

This page was built for publication: Using the minimum maximum flow degree to approximate the flow coloring problem