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

DOI10.1016/J.TCS.2012.06.037MaRDI QIDQ393134zbMATH OpenOpenAlexWikidataFDO

Authors Konstanty Junosza-Szaniawski, Jan Kratochvíl, Mathieu Liedloff, Peter Rossmanith, 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

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

Recommendations

• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• On improved exact algorithms for \(L(2,1)\)-labeling of graphs
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• Determining the \(L(2,1)\)-span in polynomial space
• Exact Algorithms for L(2,1)-Labeling of Graphs

Cites work

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

Cited in

(9)

• Exact Algorithms for L(2,1)-Labeling of Graphs
• Lower bounds for the graph homomorphism problem
• Fast exact algorithm for \(L(2,1)\)-labeling of graphs
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• On improved exact algorithms for \(L(2,1)\)-labeling of graphs
• A Very Fast Algorithm for Simultaneously Performing Connected-Component Labeling and Euler Number Computing
• Determining the \(L(2,1)\)-span in polynomial space
• Assigning channels via the meet-in-the-middle approach
• Exact algorithm for graph homomorphism and locally injective graph homomorphism

This page was built for publication: Fast exact algorithm for \(L(2,1)\)-labeling of graphs

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