Improved vertex cover algorithms for fixed genus graphs through genus reduction and planar separation /
There have been increasing efforts to find improved solutions to the VERTEX COVER problem and other NP-hard problems. The latest solving algorithms have shown progress in reducing the theoretical worst-case time complexity of finding solutions, and have also proven to be invaluable in practical app...
| Main Author: | |
|---|---|
| Format: | Thesis eBook |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
2003.
|
| Subjects: | |
| Online Access: | Link to OAKTrust copy |
| Summary: | There have been increasing efforts to find improved solutions to the VERTEX COVER problem and other NP-hard problems. The latest solving algorithms have shown progress in reducing the theoretical worst-case time complexity of finding solutions, and have also proven to be invaluable in practical applications. In this thesis, we take a new approach to solving VERTEX COVER by utilizing the topological properties of graphs. For graphs of fixed genus, we present algorithms to solve the parameterized VERTEX COVER problem in time O(kn+k³)+2⁰(vk) . |
|---|---|
| Item Description: | "Major subject: Computer Science". Vita. |
| Physical Description: | v, 44 leaves ; 28 cm. Also available online. Issued also on microfiche from Lange Micrographics. |
| Bibliography: | Includes bibliographical references (leaves 42-43). |