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

DOI10.1007/978-3-540-70575-8_25MaRDI QIDQ3521928zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Distance Constrained Labelings of Trees
• L(2,1,1)-labeling is NP-complete for trees
• scientific article; zbMATH DE number 2044507
• scientific article; zbMATH DE number 1420920
• Automata, Languages and Programming

Cited in

(26)

• The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
• Computing the nearest neighbor interchange metric for unlabeled binary trees is NP-complete
• On the computational complexity of the rooted subtree prune and regraft distance
• Systems of distant representatives
• The complexity of \(L(p, q)\)-edge-labelling
• A linear time algorithm for L(2,1)-labeling of trees
• Parameterized complexity of distance labeling and uniform channel assignment problems
• Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
• Lower bounds for the graph homomorphism problem
• Distance Constrained Labelings of Trees
• Compact Separator Decompositions in Dynamic Trees and Applications to Labeling Schemes
• L(2,1,1)-labeling is NP-complete for trees
• The (p,q)-total labeling problem for trees
• Distance three labelings of trees
• scientific article; zbMATH DE number 2044507 (Why is no real title available?)
• scientific article; zbMATH DE number 1420920 (Why is no real title available?)
• Computing L(p,1)-Labeling with Combined Parameters
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Graph-Theoretic Concepts in Computer Science
• Automata, Languages and Programming
• Fixed-parameter complexity of \(\lambda\)-labelings
• The complexity of L(p, q)-edge-labelling
• Injective colorings with arithmetic constraints
• On the complexity of labeled oriented trees
• \(L(j,k)\)-labelling and maximum ordering-degrees for trees
• The \(L(h,1,1)\)-labelling problem for trees

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

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