New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs

Details New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs

2009-04-17

arxiv.org/abs/0904.2712v1

Computer Science

Data Structures and Algorithms

The paper was presented at the 2nd annual meeting of asian association for algorithms and computation (AAAC 2009), April 11-12

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Branching Rules: Improvements on Independent Set and Vertex Cover in Sparse Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-141561