# zbMATH — the first resource for mathematics

Parameterized complexity of distance labeling and uniform channel assignment problems. (English) Zbl 1395.05143
Summary: We rephrase the distance labeling problem as a specific uniform variant of the channel assignment problem and show that the latter one is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, the distance labeling problem is $$\mathsf{FPT}$$ when parameterized by the neighborhood diversity, the maximum $$p_i$$ and $$k$$. This is indeed a more general answer to an open question of J. Fiala et al. [Lect. Notes Comput. Sci. 5532, 221–230 (2009; Zbl 1241.68071)].
Finally, we show that the uniform variant of the channel assignment problem becomes $$\mathsf{NP}$$-complete when generalized to graphs of bounded clique width.

##### MSC:
 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C82 Small world graphs, complex networks (graph-theoretic aspects) 05C12 Distance in graphs 90B80 Discrete location and assignment
Full Text:
##### References:
  Bodlaender, Hans L.; Kloks, Ton; Tan, Richard B.; Leeuwen, Jan van, $$\lambda$$-coloring of graphs, (Reichel, Horst; Tison, Sophie, STACS, Lecture Notes in Computer Science, vol. 1770, (2000), Springer), 395-406 · Zbl 0982.05050  Chang, Gerald J.; Kuo, David, The $$L(2, 1)$$-labeling problem on graphs, SIAM J. Discrete Math., 9, 2, 309-316, (1996) · Zbl 0860.05064  Corneil, Derek C.; Rotics, Udi, On the relationship between clique-width and treewidth, SIAM J. Comput., 34, 4, 825-847, (2005) · Zbl 1069.05067  Courcelle, Bruno; Olariu, Stephan, Upper bounds to the clique width of graphs, Discrete Appl. Math., 101, 1-3, 77-114, (2000) · Zbl 0958.05105  Downey, Rodney G.; Fellows, Michael R., Parameterized complexity, (1999), Springer-Verlag · Zbl 0961.68533  Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan, Distance constrained labelings of graphs of bounded treewidth, (Caires, Luís; Italiano, Giuseppe F.; Monteiro, Luís; Palamidessi, Catuscia; Yung, Moti, ICALP, Lecture Notes in Computer Science, vol. 3580, (2005), Springer), 360-372 · Zbl 1082.68080  Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan, Computational complexity of the distance constrained labeling problem for trees (extended abstract), (Aceto, Luca; Damgård, Ivan; Goldberg, Leslie Ann; Halldórsson, Magnús M.; Ingólfsdóttir, Anna; Walukiewicz, Igor, ICALP (1), Lecture Notes in Computer Science, vol. 5125, (2008), Springer), 294-305 · Zbl 1153.68390  Fiala, Jiří; Golovach, Petr A.; Kratochvíl, Jan, Parameterized complexity of coloring problems: treewidth versus vertex cover, Theoret. Comput. Sci., 412, 23, 2513-2523, (2011) · Zbl 1216.68127  Fiala, Jiří; Kratochvíl, Jan; Kloks, Ton, Fixed-parameter complexity of $$\lambda$$-labelings, Discrete Appl. Math., 113, 1, 59-72, (2001) · Zbl 0982.05085  Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket, Intractability of clique-width parameterizations, SIAM J. Comput., 39, 5, 1941-1956, (2010) · Zbl 1207.68161  Frank, András; Tardos, Éva, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, 7, 1, 49-65, (1987) · Zbl 0641.90067  Gajarský, Jakub; Lampis, Michael; Ordyniak, Sebastian, Parameterized algorithms for modular-width, (Gutin, Gregory; Szeider, Stefan, Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8246, (2013), Springer), 163-176 · Zbl 1406.68080  Ganian, Robert; Obdržálek, Jan, Expanding the expressive power of monadic second-order logic on restricted graph classes, (Lecroq, Thierry; Mouchard, Laurent, Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8288, (2013), Springer), 164-177 · Zbl 1284.68463  Griggs, Jerrold R.; Yeh, Roger K., Labelling graphs with a condition at distance 2, SIAM J. Discrete Math., 5, 4, 586-595, (1992) · Zbl 0767.05080  Gurski, Frank; Wanke, Egon, The NLC-width and clique-width for powers of graphs of bounded tree-width, Discrete Appl. Math., 157, 4, 583-595, (2009) · Zbl 1173.05342  Kobler, Daniel; Rotics, Udi, Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract), (Symposium on Discrete Algorithms, 12th SODA’01, Washington, (2001), ACM-SIAM), 468-476 · Zbl 0999.05092  Král, Daniel, The channel assignment problem with variable weights, SIAM J. Discrete Math., 20, 3, 690-704, (2006) · Zbl 1146.94003  Lampis, Michael, Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64, 1, 19-37, (2012) · Zbl 1252.68154  Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 4, 538-548, (1983) · Zbl 0524.90067  McDiarmid, Colin; Reed, Bruce, Channel assignment on graphs of bounded treewidth, Discrete Math., 273, 1-3, 183-192, (2003) · Zbl 1029.05150  Škvarek, Marián, The channel assignment problem for series-parallel graphs, (2010), Charles University Prague, (in Czech)  Wanke, Egon, $$k$$-NLC graphs and polynomial algorithms, Discrete Appl. Math., 54, 2-3, 251-266, (1994) · Zbl 0812.68106
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.