A Note on Exact Algorithms for Vertex Ordering Problems on Graphs
| dc.contributor.author | Bodlaender, Hans L. | eng |
| dc.contributor.author | Fomin, Fedor | eng |
| dc.contributor.author | Koster, Arie M.C.A. | eng |
| dc.contributor.author | Kratsch, Dieter | eng |
| dc.contributor.author | Thilikos, Dimitrios M. | eng |
| dc.date.accessioned | 2011-03-09T10:18:57Z | |
| dc.date.available | 2011-03-09T10:18:57Z | |
| dc.date.issued | 2011-01-21 | eng |
| dc.Published | Theory of Computing Systems 1-13 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1956/4556 | |
| dc.description.abstract | In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply. | en_US |
| dc.language.iso | eng | eng |
| dc.publisher | Springer | en_US |
| dc.rights | Attribution-NonCommercial CC BY-NC | eng |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc/2.5/ | eng |
| dc.subject | Graphs | eng |
| dc.subject | Algorithms | eng |
| dc.subject | Exponential time algorithms | eng |
| dc.subject | Exact algorithms | eng |
| dc.subject | Vertex ordering problems | eng |
| dc.title | A Note on Exact Algorithms for Vertex Ordering Problems on Graphs | en_US |
| dc.type | Peer reviewed | |
| dc.type | Journal article | |
| dc.description.version | publishedVersion | en_US |
| dc.rights.holder | The Author(s) 2011 | en_US |
| dc.rights.holder | Copyright The Author(s) 2011. This article is published with open access at Springerlink.com | en_US |
| dc.identifier.doi | https://doi.org/10.1007/s00224-011-9312-0 | |
| dc.identifier.cristin | 922996 | |
| dc.subject.nsi | VDP::Mathematics and natural science: 400 | en_US |
Tilhørende fil(er)
Denne innførselen finnes i følgende samling(er)
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution-NonCommercial CC BY-NC