Complexity of graph covering problems

DOI10.1007/3-540-59071-4_40MaRDI QIDQ6184361zbMATH OpenFDO

Authors Jan Kratochvíl, Andrzej Proskurowski, Jan Arne Telle

Publication date 5 January 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59071-4_40

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1236360
• Covering regular graphs
• scientific article; zbMATH DE number 1107736
• scientific article; zbMATH DE number 89406
• scientific article; zbMATH DE number 2081019

Cites work

• Coverings and minors: Application to local computations in graphs
• Finite common coverings of graphs
• Finite common coverings of pairs of regular graphs
• scientific article; zbMATH DE number 91031 (Why is no real title available?)
• scientific article; zbMATH DE number 3445271 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• On the complexity of H-coloring
• The NP-Completeness of Edge-Coloring

Cited in

(13)

• On the weighted complexity of a regular covering of a graph
• Computational complexity of covering disconnected multigraphs
• On the computational complexity of partial covers of theta graphs
• Complexity results for well‐covered graphs
• scientific article; zbMATH DE number 89406 (Why is no real title available?)
• scientific article; zbMATH DE number 1236360 (Why is no real title available?)
• Computational complexity of covering cyclic graphs
• scientific article; zbMATH DE number 7724194 (Why is no real title available?)
• Computational Complexity of Covering Colored Mixed Multigraphs with Degree Partition Equivalence Classes of Size at Most Two (Extended Abstract)
• Computational complexity of covering disconnected multigraphs
• Computational complexity of covering coloured mixed multigraphs with simple degree partitions
• Computational complexity of covering regular trees
• The complexity of the covering radius problem

This page was built for publication: Complexity of graph covering problems

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