Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems

DOI10.1007/978-3-319-42634-1_6zbMATH Open1476.68207arXiv1507.00640OpenAlexW2499245161WikidataQ62044474 ScholiaQ62044474MaRDI QIDQ2817849FDOQ2817849

Jan Kratochvíl, Jiří Fiala, Dušan Knop, Tomáš Gavenčiak, Martin Koutecký

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We study computational complexity of the class of distance-constrained graph labeling problems from the fixed parameter tractability point of view. The parameters studied are neighborhood diversity and clique width. We rephrase the distance constrained graph labeling problem as a specific uniform variant of the Channel Assignment problem and show that this problem is fixed parameter tractable when parameterized by the neighborhood diversity together with the largest weight. Consequently, every $L(p_1,p_2,dots,p_k)$-labeling problem is FPT when parameterized by the neighborhood diversity, the maximum $p_i$ and $k.$ Our results yield also FPT algorithms for all $L(p_1,p_2,dots,p_k)$-labeling problems when parameterized by the size of a minimum vertex cover, answering an open question of Fiala et al.: Parameterized complexity of coloring problems: Treewidth versus vertex cover. The same consequence applies on Channel Assignment when the maximum weight is additionally included among the parameters. Finally, we show that the uniform variant of the Channel Assignment problem becomes NP-complete when generalized to graphs of bounded clique width.

Full work available at URL: https://arxiv.org/abs/1507.00640

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Title not available (Why is that?)
• Algorithmic meta-theorems for restrictions of treewidth
• Upper bounds to the clique width of graphs
• Integer Programming with a Fixed Number of Variables
• On the Relationship Between Clique-Width and Treewidth
• Labelling Graphs with a Condition at Distance 2
• An application of simultaneous diophantine approximation in combinatorial optimization
• Parameterized Algorithms for Modular-Width
• Intractability of Clique-Width Parameterizations
• The $L(2,1)$-Labeling Problem on Graphs
• Fixed-parameter complexity of \(\lambda\)-labelings
• \(k\)-NLC graphs and polynomial algorithms
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Automata, Languages and Programming
• The Channel Assignment Problem with Variable Weights
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Channel assignment on graphs of bounded treewidth
• Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)

Cited In (2)

• Optimal channel assignment and \(L(p,1)\)-labeling
• Iterated Type Partitions

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Tight lower bound for the channel assignment problem 👍 👎
• Approximation algorithms for channel assignment with constraints 👍 👎
• \(L(p,q)\)-label coloring problem with application to channel allocation 👍 👎
• Tight Lower Bound for the Channel Assignment Problem 👍 👎
• Optimal channel assignment and \(L(p,1)\)-labeling 👍 👎
• Channel assignment problem and \(n\)-fold \(t\)-separated \(L(j_1,j_2,\dots,j_m)\)-labeling of graphs 👍 👎
• Parameterized complexity of distance labeling and uniform channel assignment problems 👍 👎
• Channel assignment problem and relaxed 2-distant coloring of graphs 👍 👎

This page was built for publication: Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817849)