Exact algorithms for \(L(2,1)\)-labeling of graphs

DOI10.1007/s00453-009-9302-7zbMath1213.68455OpenAlexW2080290639MaRDI QIDQ627538

Frédéric Havet, Mathieu Liedloff, Dieter Kratsch, Martin Klazar, Jan Kratochvíl

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9302-7

zbMATH Keywords

algorithmgraph\(L(2,1)\)-labelingmoderately exponential time algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (16)

Lower Bounds for the Graph Homomorphism Problem ⋮ Colorings with few colors: counting, enumeration and combinatorial bounds ⋮ Threshold-coloring and unit-cube contact representation of planar graphs ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Distance three labelings of trees ⋮ On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Channel assignment via fast zeta transform ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism ⋮ Determining the \(L(2,1)\)-span in polynomial space ⋮ On Improved Exact Algorithms for L(2,1)-Labeling of Graphs ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ \(L(2, 1)\)-labelling of graphs with few \(P_4\)'s ⋮ On the number of 2-packings in a connected graph ⋮ Star-factors in graphs with large minimum degree ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Spanning trees without adjacent vertices of degree 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• On generating all maximal independent sets
• Cyclic labellings with constraints at two distances
• Exact algorithms for graph homomorphisms
• An $\mbox{O}(n^{1.75})$ Algorithm for L(2,1)-Labeling of Trees
• Exact Algorithms for L(2,1)-Labeling of Graphs
• Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings
• Labelling Graphs with a Condition at Distance 2
• Approximations for  -Colorings of Graphs
• Partial covers of graphs
• The $L(2,1)$-Labeling Problem on Graphs
• Multilevel Distance Labelings for Paths and Cycles
• Automata, Languages and Programming
• Automata, Languages and Programming
• The Channel Assignment Problem with Variable Weights
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: Exact algorithms for \(L(2,1)\)-labeling of graphs