Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)

DOI10.1007/978-3-540-70575-8_25zbMath1153.68390OpenAlexW1586990653MaRDI QIDQ3521928

Petr A. Golovach, Jan Kratochvíl, Jiří Fiala

Publication date: 28 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-70575-8_25

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (14)

Lower Bounds for the Graph Homomorphism Problem ⋮ Computing L(p,1)-Labeling with Combined Parameters ⋮ A linear time algorithm for \(L(2,1)\)-labeling of trees ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ The \((p,q)\)-total labeling problem for trees ⋮ Injective colorings with arithmetic constraints ⋮ Distance three labelings of trees ⋮ Parameterized complexity of coloring problems: treewidth versus vertex cover ⋮ \(L(j,k)\)-labelling and maximum ordering-degrees for trees ⋮ The \(L(h,1,1)\)-labelling problem for trees ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree

This page was built for publication: Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)