Parameterized complexity of distance labeling and uniform channel assignment problems

DOI10.1016/J.DAM.2017.02.010MaRDI QIDQ2413966zbMATH OpenOpenAlexWikidataFDO

Authors Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, Jan Kratochvíl, 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

channel assignmentfixed parameter tractabilitydistance labelingbounded vertex coverbounded cliquewidth

Mathematics Subject Classification ID

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

Recommendations

• Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
• Fixed-parameter complexity of \(\lambda\)-labelings
• Publication:4944992

Cites work

• scientific article; zbMATH DE number 1500531 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• 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
• 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
• \(k\)-NLC graphs and polynomial algorithms

Cited in

(8)

• Combinatorial \(n\)-fold integer programming and applications
• Parameterized complexity for iterated type partitions and modular-width
• Computing \(L(p, 1)\)-labeling with combined parameters
• Getting linear time in graphs of bounded neighborhood diversity
• Integer programming in parameterized complexity: three miniatures
• Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
• Computing L(p,1)-Labeling with Combined Parameters
• Combinatorial \(n\)-fold integer programming and applications

This page was built for publication: Parameterized complexity of distance 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 Q2413966)