J. Chalopin
Packing bipartite graphs with covers of complete bipartite graphs
Chalopin, J.; Paulusma, D.
Authors
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Contributors
Tiziana Calamoneri
Editor
Josep Diaz
Editor
Abstract
For a set of graphs, a perfect -packing (-factor) of a graph G is a set of mutually vertex-disjoint subgraphs of G that each are isomorphic to a member of and that together contain all vertices of G. If G allows a covering (locally bijective homomorphism) to a graph H, then G is an H-cover. For some fixed H let consist of all H-covers. Let K k,ℓ be the complete bipartite graph with partition classes of size k and ℓ, respectively. For all fixed k,ℓ ≥ 1, we determine the computational complexity of the problem that tests if a given bipartite graph has a perfect -packing. Our technique is partially based on exploring a close relationship to pseudo-coverings. A pseudo-covering from a graph G to a graph H is a homomorphism from G to H that becomes a covering to H when restricted to a spanning subgraph of G. We settle the computational complexity of the problem that asks if a graph allows a pseudo-covering to K k,ℓ for all fixed k,ℓ ≥ 1.
Citation
Chalopin, J., & Paulusma, D. (2010). Packing bipartite graphs with covers of complete bipartite graphs. In T. Calamoneri, & J. Diaz (Eds.), Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings (276-287). https://doi.org/10.1007/978-3-642-13073-1_25
Conference Name | 7th International Conference on Algorithms and Complexity |
---|---|
Conference Location | Rome, Italy |
Publication Date | Jan 1, 2010 |
Deposit Date | Oct 6, 2010 |
Publisher | Springer Verlag |
Pages | 276-287 |
Series Title | Lecture notes in computer science |
Series Number | 6078 |
Edition | 7th |
Book Title | Algorithms and complexity, 7th International Conference, CIAC 2010, 26-28 May 2010, Rome, Italy ; proceedings. |
DOI | https://doi.org/10.1007/978-3-642-13073-1_25 |
Public URL | https://durham-repository.worktribe.com/output/1159326 |
You might also like
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
An algorithmic framework for locally constrained homomorphisms
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search