New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs
| dc.creator | Xiao, Mingyu | |
| dc.date | 2009-04-17 | |
| dc.date.accessioned | 2026-07-07T13:05:42Z | |
| dc.date.available | 2026-07-07T13:05:42Z | |
| dc.description | We present an $O^*(1.0919^n)$-time algorithm for finding a maximum independent set in an $n$-vertex graph with degree bounded by 3, which improves the previously known algorithm of running time $O^*(1.0977^n)$ by Bourgeois, Escoffier and Paschos [IWPEC 2008]. We also present an $O^*(1.1923^k)$-time algorithm to decide if a graph with degree bounded by 3 has a vertex cover of size $k$, which improves the previously known algorithm of running time $O^*(1.1939^k)$ by Chen, Kanj and Xia [ISAAC 2003]. Two new branching techniques, \emph{branching on a bottle} and \emph{branching on a 4-cycle}, are introduced, which help us to design simple and fast algorithms for the maximum independent set and minimum vertex cover problems and avoid tedious branching rules. | |
| dc.description | The paper was presented at the 2nd annual meeting of asian association for algorithms and computation (AAAC 2009), April 11-12, 2009, Hangzhou, China | |
| dc.identifier | https://arxiv.org/abs/0904.2712 | |
| dc.identifier | http://arxiv.org/abs/0904.2712 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/227571 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs | |
| dc.type | text |