Fast exact algorithm for \(L(2,1)\)-labeling of graphs

DOI10.1016/j.tcs.2012.06.037zbMath1417.05214OpenAlexW2178461450WikidataQ62595918 ScholiaQ62595918MaRDI QIDQ393134

Jan Kratochvíl, Konstanty Junosza-Szaniawski, Peter Rossmanith, Mathieu Liedloff, Paweł Rzążewski

Publication date: 16 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://zenodo.org/record/895791

zbMATH Keywords

exponential-time algorithm\(L(21)\)-labeling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Assigning channels via the meet-in-the-middle approach ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Exact algorithm for graph homomorphism and locally injective graph homomorphism

Cites Work

• Unnamed Item
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
• Exact exponential algorithms.
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Graph labellings with variable weights, a survey
• The complexity of the \(L(p,q)\)-labeling problem for bipartite planar graphs of small degree
• On the complexity of exact algorithm for \(L(2,1)\)-labeling of graphs
• Channel assignment via fast zeta transform
• A survey on labeling graphs with a condition at distance two
• Gaussian elimination is not optimal
• On Improved Exact Algorithms for L(2,1)-Labeling of Graphs
• Fast Exact Algorithm for L(2,1)-Labeling of Graphs
• High degree graphs contain large-star factors
• A measure & conquer approach for the analysis of exact algorithms
• Exact Algorithms for L(2,1)-Labeling of Graphs
• A Linear Time Algorithm for L(2,1)-Labeling of Trees
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Labelling Graphs with a Condition at Distance 2
• Graph Classes: A Survey
• Approximations for  -Colorings of Graphs
• The $L(2,1)$-Labeling Problem on Graphs
• Automata, Languages and Programming
• Automata, Languages and Programming
• The Channel Assignment Problem with Variable Weights
• Fixed-parameter complexity of \(\lambda\)-labelings