Computational complexity of distance edge labeling

DOI10.1016/j.dam.2017.01.007zbMath1390.05204arXiv1508.01014MaRDI 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 complexity; exponential time hypothesis; line-graphs; distance labeling

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C76: Graph operations (line graphs, products, etc.)

Uses Software

• CALMA