Parameterized complexity of distance labeling and uniform channel assignment problems

DOI10.1016/j.dam.2017.02.010zbMath1395.05143OpenAlexW2598280710WikidataQ62044476 ScholiaQ62044476MaRDI QIDQ2413966

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

Publication date: 17 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2017.02.010

zbMATH Keywords

fixed parameter tractabilitychannel assignmentdistance labelingbounded vertex coverbounded cliquewidth

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Discrete location and assignment (90B80) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (7)

Computing L(p,1)-Labeling with Combined Parameters ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Computing \(L(p, 1)\)-labeling with combined parameters ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Unnamed Item

Cites Work

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

This page was built for publication: Parameterized complexity of distance labeling and uniform channel assignment problems