F.R. Madelaine
Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies
Madelaine, F.R.; Stewart, I.A.
Abstract
We improve upon the best known upper and lower bounds on the sizes of minimal feedback vertex sets in butterflies. Also, we construct new feedback vertex sets in grids so that for a large number of pairs $(n,m)$, the size of our feedback vertex set in the grid $M_{n,m}$ matches the best known lower bound, and for all other pairs it differs from this lower bound by at most 2.
Citation
Madelaine, F., & Stewart, I. (2008). Improved upper and lower bounds on the feedback vertex numbers of grids and butterflies. Discrete Mathematics, 308(18), 4144-4164. https://doi.org/10.1016/j.disc.2007.08.007
Journal Article Type | Article |
---|---|
Publication Date | Sep 1, 2008 |
Deposit Date | Jun 29, 2009 |
Publicly Available Date | Jun 29, 2009 |
Journal | Discrete mathematics. |
Print ISSN | 0012-365X |
Electronic ISSN | 2578-9252 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 308 |
Issue | 18 |
Pages | 4144-4164 |
DOI | https://doi.org/10.1016/j.disc.2007.08.007 |
Keywords | Feedback vertex set, Grids, Butterflies. |
Public URL | https://durham-repository.worktribe.com/output/1553374 |
Publisher URL | http://www.dur.ac.uk/i.a.stewart/Papers/FVSGridsAndButterflies.pdf |
Files
Accepted Journal Article
(347 Kb)
PDF
You might also like
Routing algorithms for recursively-defined data centre networks
(2015)
Presentation / Conference Contribution
Accelerating ant colony optimization-based edge detection on the GPU using CUDA
(2014)
Presentation / Conference Contribution
Improved routing in the data centre networks HCN and BCN
(2014)
Presentation / Conference Contribution
Improving Ant Colony Optimization performance on the GPU using CUDA.
(2013)
Presentation / Conference Contribution
Color image edge detection based on quantity of color information and implementation on the GPU.
(2011)
Presentation / Conference Contribution
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