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.

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: DOI
[1] 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
[2] 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
[3] Corneil, Derek C.; Rotics, Udi, On the relationship between clique-width and treewidth, SIAM J. Comput., 34, 4, 825-847, (2005) · Zbl 1069.05067
[4] Courcelle, Bruno; Olariu, Stephan, Upper bounds to the clique width of graphs, Discrete Appl. Math., 101, 1-3, 77-114, (2000) · Zbl 0958.05105
[5] Downey, Rodney G.; Fellows, Michael R., Parameterized complexity, (1999), Springer-Verlag · Zbl 0961.68533
[6] 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
[7] 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
[8] 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
[9] Fiala, Jiří; Kratochvíl, Jan; Kloks, Ton, Fixed-parameter complexity of \(\lambda\)-labelings, Discrete Appl. Math., 113, 1, 59-72, (2001) · Zbl 0982.05085
[10] 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
[11] Frank, András; Tardos, Éva, An application of simultaneous Diophantine approximation in combinatorial optimization, Combinatorica, 7, 1, 49-65, (1987) · Zbl 0641.90067
[12] 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
[13] 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
[14] 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
[15] 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
[16] 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
[17] Král, Daniel, The channel assignment problem with variable weights, SIAM J. Discrete Math., 20, 3, 690-704, (2006) · Zbl 1146.94003
[18] Lampis, Michael, Algorithmic meta-theorems for restrictions of treewidth, Algorithmica, 64, 1, 19-37, (2012) · Zbl 1252.68154
[19] Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 4, 538-548, (1983) · Zbl 0524.90067
[20] McDiarmid, Colin; Reed, Bruce, Channel assignment on graphs of bounded treewidth, Discrete Math., 273, 1-3, 183-192, (2003) · Zbl 1029.05150
[21] Škvarek, Marián, The channel assignment problem for series-parallel graphs, (2010), Charles University Prague, (in Czech)
[22] 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.