Distance constrained labelings of graphs of bounded treewidth

DOI10.1007/11523468_30MaRDI QIDQ5716789zbMATH OpenOpenAlexFDO

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

Publication date 10 January 2006

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

Full work available at URL https://doi.org/10.1007/11523468

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• L(2,1,1)-labeling is NP-complete for trees
• Exact Algorithms for L(2,1)-Labeling of Graphs
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Distance three labelings of trees
• Theoretical Computer Science

Cited in

(32)

• The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
• Labeling bipartite permutation graphs with a condition at distance two
• Distance constrained labelings of \(K_{4}\)-minor free graphs
• \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s
• Constrained-path labellings on graphs of bounded clique-width
• Computing \(L(p, 1)\)-labeling with combined parameters
• On the intersection graph of the disks with diameters the sides of a convex \(n\)-gon
• A linear time algorithm for L(2,1)-labeling of trees
• Parameterized complexity of distance labeling and uniform channel assignment problems
• Determining the \(L(2,1)\)-span in polynomial space
• \(L(2, 1)\)-labeling of the Cartesian and strong product of two directed cycles
• Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Distance Constrained Labelings of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-minor Free Graphs
• Distance Constrained Labelings of Trees
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
• Fast exact algorithm for L(2,1)-labeling of graphs
• Distance three labelings of trees
• Computing L(p,1)-Labeling with Combined Parameters
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• L(2,1)-labeling for brick product graphs
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• An 8-approximation algorithm for \(L(2 ,1)\)-labeling of unit disk graphs
• Tangle bases: Revisited
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• A linear algorithm for radio k-coloring of powers of paths having small diameters
• \textsc{Telephone Broadcast} on graphs of treewidth two
• Equitable colorings of bounded treewidth graphs
• An O\((n^{1.75})\) algorithm for \(L(2,1)\)-labeling of trees
• The \(L(h,1,1)\)-labelling problem for trees
• Comparing universal covers in polynomial time

This page was built for publication: Distance constrained labelings of graphs of bounded treewidth

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