Show simple item record

A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

dc.contributor.authorBodlaender, Hans L.eng
dc.contributor.authorFomin, Fedoreng
dc.contributor.authorKoster, Arie M.C.A.eng
dc.contributor.authorKratsch, Dietereng
dc.contributor.authorThilikos, Dimitrios M.eng
dc.date.accessioned2011-03-09T10:18:57Z
dc.date.available2011-03-09T10:18:57Z
dc.date.issued2011-01-21eng
dc.PublishedTheory of Computing Systems 1-13en_US
dc.identifier.urihttps://hdl.handle.net/1956/4556
dc.description.abstractIn 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.isoengeng
dc.publisherSpringeren_US
dc.rightsAttribution-NonCommercial CC BY-NCeng
dc.rights.urihttp://creativecommons.org/licenses/by-nc/2.5/eng
dc.subjectGraphseng
dc.subjectAlgorithmseng
dc.subjectExponential time algorithmseng
dc.subjectExact algorithmseng
dc.subjectVertex ordering problemseng
dc.titleA Note on Exact Algorithms for Vertex Ordering Problems on Graphsen_US
dc.typePeer reviewed
dc.typeJournal article
dc.description.versionpublishedVersionen_US
dc.rights.holderThe Author(s) 2011en_US
dc.rights.holderCopyright The Author(s) 2011. This article is published with open access at Springerlink.comen_US
dc.identifier.doihttps://doi.org/10.1007/s00224-011-9312-0
dc.identifier.cristin922996
dc.subject.nsiVDP::Mathematics and natural science: 400en_US


Files in this item

Thumbnail
Name:
A Note on Exact Algorithms for ...
Size:
312.4Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial CC BY-NC
Except where otherwise noted, this item's license is described as Attribution-NonCommercial CC BY-NC