%0 Conference Paper %1 gao2017scaling %A Gao, Wanru %A Friedrich, Tobias %A Kötzing, Timo %A Neumann, Frank %B Australasian Conference on Artificial Intelligence (AUSAI) %D 2017 %K testing typo3 %T Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization %X We investigate how well-performing local search algorithms for small or medium size instances can be scaled up to perform well for large inputs. We introduce a parallel kernelization technique that is motivated by the assumption that graphs in medium to large scale are composed of components which are on their own easy for state-of-the-art solvers but when hidden in large graphs are hard to solve. To show the effectiveness of our kernelization technique, we consider the well-known minimum vertex cover problem and two state-of-the-art solvers called NuMVC and FastVC. Our kernelization approach reduces an existing large problem instance significantly and produces better quality results on a wide range of benchmark instances and real world graphs.

@inproceedings{gao2017scaling, abstract = {We investigate how well-performing local search algorithms for small or medium size instances can be scaled up to perform well for large inputs. We introduce a parallel kernelization technique that is motivated by the assumption that graphs in medium to large scale are composed of components which are on their own easy for state-of-the-art solvers but when hidden in large graphs are hard to solve. To show the effectiveness of our kernelization technique, we consider the well-known minimum vertex cover problem and two state-of-the-art solvers called NuMVC and FastVC. Our kernelization approach reduces an existing large problem instance significantly and produces better quality results on a wide range of benchmark instances and real world graphs.}, added-at = {2017-09-19T19:34:51.000+0200}, author = {Gao, Wanru and Friedrich, Tobias and Kötzing, Timo and Neumann, Frank}, biburl = {https://www.bibsonomy.org/bibtex/2ce8d860d251868d401eaba84eda9ec75/typo3tester}, booktitle = {Australasian Conference on Artificial Intelligence (AUSAI)}, interhash = {296438c43915e50db2df335569a0fc5c}, intrahash = {ce8d860d251868d401eaba84eda9ec75}, keywords = {testing typo3}, timestamp = {2017-09-19T19:34:51.000+0200}, title = {Scaling up Local Search for Minimum Vertex Cover in Large Graphs by Parallel Kernelization}, year = 2017 }