A computational complexity comparative study of graph tessellation problems

DOI10.1016/j.tcs.2020.11.045zbMath1462.68129OpenAlexW3109365446MaRDI QIDQ2222093

Yanyan Li

Publication date: 3 February 2021

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.11.045

zbMATH Keywords

computational complexitystructural graph theoryequivalence coveringtessellation cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Total tessellation cover: bounds, hardness, and applications

Cites Work

• Unnamed Item
• Unnamed Item
• The staggered quantum walk model
• Covering line graphs with equivalence relations
• On the equivalence covering number of splitgraphs
• The ellipsoid method and its consequences in combinatorial optimization
• The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness
• The graph tessellation cover number: extremal bounds, efficient algorithms and hardness
• Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint)
• The chromatic index of graphs with a spanning star

This page was built for publication: A computational complexity comparative study of graph tessellation problems