Computer Science – Data Structures and Algorithms
Scientific paper
2010-09-27
Computer Science
Data Structures and Algorithms
further improvement under progress
Scientific paper
Kernelization algorithms, usually a preprocessing step before other more traditional algorithms, are very special in the sense that they return (reduced) instances, instead of final results. This characteristic excludes the freedom of applying a kernelization algorithm for the weighted version of a problem to its unweighted instances. Thus with only very few special cases, kernelization algorithms have to be studied separately for weigthed and unweighted versions of a single problem. {\sc feedback arc set on tournament} is currently a very popular problem in recent research of parameterized, as well as approximation computation, and its wide applications in many areas make it appear in all top conferences. The theory of graph modular decompositions is a general approach in the study of graph structures, which only had its surfaces touched in previous work on kernelization algorithms of {\sc feedback arc set on tournament}. In this paper, we study further properties of graph modular decompositions and apply them to obtain the first linear kernel for the unweighted {\sc feedback arc set on tournament} problem, which only admits linear kernel in its weighted version, while quadratic kernel for the unweighted.
Cao Yixin
Chen Jianer
No associations
LandOfFree
FAST: Kernelization based on Graph Modular Decomposition 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 FAST: Kernelization based on Graph Modular Decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FAST: Kernelization based on Graph Modular Decomposition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-517112