Computational complexity of distance edge labeling

DOI10.1016/j.dam.2017.01.007zbMath1390.05204arXiv1508.01014OpenAlexW2208454890MaRDI QIDQ1647838

Tomáš Masařík, Dušan Knop

Publication date: 27 June 2018

Published in: Discrete Applied Mathematics, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.01014

zbMATH Keywords

computational complexityexponential time hypothesisline-graphsdistance labeling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph operations (line graphs, products, etc.) (05C76)

Related Items (5)

Computational complexity of distance edge labeling ⋮ The complexity of \(L(p, q)\)-edge-labelling ⋮ Facial \(L(2, 1)\)-edge-labelings of trees ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ The complexity of \(L(p, q)\)-edge-labelling

Uses Software

• CALMA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \((p,q)\)-total labeling problem for trees
• Complexity of (p,1)-total labelling
• Which problems have strongly exponential complexity?
• Computational complexity of distance edge labeling
• \((p,1)\)-total labelling of graphs
• Parametrized complexity theory.
• On the Limits of Sparsification
• Griggs and Yeh's Conjecture and $L(p,1)$-labelings
• A survey of graph coloring - its types, methods and applications
• Known Algorithms for Edge Clique Cover are Probably Optimal
• The Complexity of Satisfiability of Small Depth Circuits
• Labelling Graphs with a Condition at Distance 2
• Approximations for  -Colorings of Graphs
• Computational Complexity
• The complexity of satisfiability problems
• Parameterized Algorithms
• Models and solution techniques for frequency assignment problems
• Fixed-parameter complexity of \(\lambda\)-labelings

This page was built for publication: Computational complexity of distance edge labeling