کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418567 | 681688 | 2015 | 18 صفحه PDF | دانلود رایگان |
Motivated by bandwidth allocation under interference constraints in radio networks, we define and investigate an optimization problem that combines the classical flow and edge coloring problems in graphs. Let G=(V,E)G=(V,E) be a graph with a demand function b:V→Z+b:V→Z+ and a gateway g∈V∖Vsg∈V∖Vs, where Vs={v∈V:b(v)>0}Vs={v∈V:b(v)>0} is the set of source nodes . A flow ϕuϕu of a source node uu is a multiset of b(u)b(u) paths in GG from uu to gg. A flow ϕϕ on GG is a set with one flow for each source node. Every flow ϕϕ defines a multigraph GϕGϕ with vertex set VV and all edges in the paths in ϕϕ. A distance- ddedge coloring of a flow ϕϕ is an edge coloring of GϕGϕ such that two edges with the same color are at distance at least dd in GG. The distance- ddflow coloring problem (FCPdFCPd) is the problem of obtaining a flow ϕϕ on GG with a distance-dd edge coloring where the number of used colors is minimum. For any fixed d≥3d≥3, we prove that FCPdFCPd is NP-hard even on a bipartite graph with just one source node. For d=2d=2, we also prove NP-hardness on a bipartite graph with multiples sources. For d=1d=1, we show that the problem is polynomial in 3-connected graphs and bipartite graphs. Finally, we show that a list version of the problem is inapproximable in polynomial time by a factor of O(logn)O(logn) even on nn-vertex paths, for any d≥1d≥1.
Journal: Discrete Applied Mathematics - Volume 197, 31 December 2015, Pages 75–92