Complexity of partial covers of graphs

DOI10.1007/3-540-45678-3_46MaRDI QIDQ4474120zbMATH OpenFDO

Authors Jiří Fiala, Jan Kratochvíl

Publication date 4 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2223/22230537.htm

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

• Partial covers of graphs
• scientific article; zbMATH DE number 1236360
• Complexity of colored graph covers. I: Colored directed multigraphs
• Covering regular graphs
• Generalized H-coloring and H-covering of trees

Cited in

(36)

• Covering regular graphs
• On the weighted complexity of a regular covering of a graph
• List covering of regular multigraphs
• Locally constrained graph homomorphisms and equitable partitions
• Exact algorithm for graph homomorphism and locally injective graph homomorphism
• On the computational complexity of partial covers of theta graphs
• An O(n n) algorithm for finding edge span of cacti
• Partial covering of hypergraphs
• Complexity of locally injective homomorphism to the Theta graphs
• Locally injective homomorphism to the simple weight graphs
• Loose cover of graphs by a local structure
• Distance Constrained Labelings of Trees
• Comparing Universal Covers in Polynomial Time
• 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?)
• Generalized H-coloring and H-covering of trees
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Partial covers of graphs
• scientific article; zbMATH DE number 2111730 (Why is no real title available?)
• Computational complexity of covering cyclic graphs
• List covering of regular multigraphs with semi-edges
• scientific article; zbMATH DE number 7724194 (Why is no real title available?)
• Complexity of graph covering problems
• Loose cover of graphs
• Exact algorithms for \(L(2,1)\)-labeling of graphs
• 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
• Certain subgroups of fundamental group of graphs
• Computational complexity of covering coloured mixed multigraphs with simple degree partitions
• Computing role assignments of chordal graphs
• The complexity of locally injective homomorphisms
• A complete complexity classification of the role assignment problem
• On the complexity of cover-incomparability graphs of posets
• The stochastic weighted complexity of a group covering of a digraph
• Comparing universal covers in polynomial time

This page was built for publication: Complexity of partial covers of graphs

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