File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Book Chapter: Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches

TitleFaster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches
Authors
Issue Date2013
PublisherSpringer
Citation
Faster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches. In Pardalos, PM; Du, DZ & Graham, RL (Eds.), Handbook of Combinatorial Optimization (2nd ed.), v. 2, p. 1249-1291. New York, NY: Springer, 2013 How to Cite?
AbstractExponential algorithms, whose time complexity is O(c n ) for some constant c > 1, are inevitable when exactly solving NP-complete problems unless P=NP . This chapter presents recently emerged combinatorial and algebraic techniques for designing exact exponential time algorithms. The discussed techniques can be used either to derive faster exact exponential algorithms or to significantly reduce the space requirements while without increasing the running time. For illustration, exact algorithms arising from the use of these techniques for some optimization and counting problems are given.
Persistent Identifierhttp://hdl.handle.net/10722/220521
ISBN

 

DC FieldValueLanguage
dc.contributor.authorYu, D-
dc.contributor.authorWang, Y-
dc.contributor.authorHua, QS-
dc.contributor.authorLau, FCM-
dc.date.accessioned2015-10-16T06:44:25Z-
dc.date.available2015-10-16T06:44:25Z-
dc.date.issued2013-
dc.identifier.citationFaster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches. In Pardalos, PM; Du, DZ & Graham, RL (Eds.), Handbook of Combinatorial Optimization (2nd ed.), v. 2, p. 1249-1291. New York, NY: Springer, 2013-
dc.identifier.isbn9781441979964-
dc.identifier.urihttp://hdl.handle.net/10722/220521-
dc.description.abstractExponential algorithms, whose time complexity is O(c n ) for some constant c > 1, are inevitable when exactly solving NP-complete problems unless P=NP . This chapter presents recently emerged combinatorial and algebraic techniques for designing exact exponential time algorithms. The discussed techniques can be used either to derive faster exact exponential algorithms or to significantly reduce the space requirements while without increasing the running time. For illustration, exact algorithms arising from the use of these techniques for some optimization and counting problems are given.-
dc.languageeng-
dc.publisherSpringer-
dc.relation.ispartofHandbook of Combinatorial Optimization (2nd ed.)-
dc.titleFaster and Space Efficient Exact Exponential Algorithms: Combinatorial and Algebraic Approaches-
dc.typeBook_Chapter-
dc.identifier.emailYu, D: mxyu@hku.hk-
dc.identifier.emailWang, Y: amywang@hku.hk-
dc.identifier.emailHua, QS: qshua@cs.hku.hk-
dc.identifier.emailLau, FCM: fcmlau@cs.hku.hk-
dc.identifier.authorityLau, FCM=rp00221-
dc.identifier.doi10.1007/978-1-4419-7997-1_38-
dc.identifier.hkuros255636-
dc.identifier.volume2-
dc.identifier.spage1249-
dc.identifier.epage1291-
dc.publisher.placeNew York, NY-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats