.png){kind=icon}
.png){kind=icon}
Return
Using the minimum maximum flow degree to approximate the flow coloring problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-021-04180-3.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Consider an arc-capacitated network N through which an integer-valued flow must be sent from several source nodes to a sink node. Each feasible flow defines a corresponding multi-graph with the same vertices as N and an edge for each arc ofN, where the edge multiplicity is the flow in the respective arc. The maximum flow degree of a feasible flow is the maximum sum of the flow entering and leaving a node of N, i.e. the maximum degree of the corresponding multigraph. The minimum maximum flow degree problem (MMFDP) consists in determining on N a feasible flow such that its maximum flow degree is minimum. We present a polynomial time algorithm for this problem. We use its optimum value to derive an improved upper bound for the flow coloring problem (FCP), which consists in finding a feasible flow whose corresponding multigraph has the minimum chromatic index. Based on this procedure, we design an approximation algorithm for the FCP that improves the best known approximation factor.
Keywords:
Graph algorithms
Network flow
Flow degree
Flow coloring problem
Approximation algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W