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

DOI10.1007/978-3-319-42634-1_6MaRDI QIDQ2817849zbMATH OpenOpenAlexWikidataFDO

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

Publication date 2 September 2016

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

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

Mathematics Subject Classification ID

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

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.

Recommendations

• Parameterized complexity of distance labeling and uniform channel assignment problems
• Optimal channel assignment and \(L(p,1)\)-labeling
• Approximation algorithms for channel assignment with constraints
• scientific article; zbMATH DE number 1522941
• Tight lower bound for the channel assignment problem
• Tight lower bound for the channel assignment problem
• Channel assignment problem and n-fold t-separated L(j₁,j₂,,j_m)-labeling of graphs
• L(p,q)-label coloring problem with application to channel allocation
• An approximation algorithm for channel assignment with certain constraints
• Channel assignment problem and relaxed 2-distant coloring of graphs

Cites work

• \(k\)-NLC graphs and polynomial algorithms
• Algorithmic meta-theorems for restrictions of treewidth
• An application of simultaneous diophantine approximation in combinatorial optimization
• Automata, Languages and Programming
• Channel assignment on graphs of bounded treewidth
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Expanding the expressive power of monadic second-order logic on restricted graph classes
• Fixed-parameter complexity of \(\lambda\)-labelings
• scientific article; zbMATH DE number 1500531 (Why is no real title available?)
• Integer Programming with a Fixed Number of Variables
• Intractability of clique-width parameterizations
• Labelling Graphs with a Condition at Distance 2
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms for Modular-Width
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)
• The $L(2,1)$-Labeling Problem on Graphs
• The Channel Assignment Problem with Variable Weights
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Upper bounds to the clique width of graphs

Cited in

(4)

• Optimal channel assignment and \(L(p,1)\)-labeling
• Parameterized complexity of distance labeling and uniform channel assignment problems
• Iterated Type Partitions
• Toward optimal radio colorings of hypercubes via SAT-solving

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)