Fast exact algorithm for \(L(2,1)\)-labeling of graphs
From MaRDI portal
Publication:393134
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
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
