skip to main content

Kernels for feedback arc set in tournaments

Bessy, Stéphane ; Fomin, Fedor V ; Gaspers, Serge ; Paul, Christophe ; Perez, Anthony ; Saurabh, Saket ; Thomassé, Stéphan

Journal of Computer and System Sciences, 2011, Vol.77(6), pp.1071-1078 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por
  • Título:
    Kernels for feedback arc set in tournaments
  • Autor: Bessy, Stéphane ; Fomin, Fedor V ; Gaspers, Serge ; Paul, Christophe ; Perez, Anthony ; Saurabh, Saket ; Thomassé, Stéphan
  • Assuntos: Feedback Arc Set ; Tournaments ; Kernelization ; Parameterized Algorithms ; Graph Algorithms ; Engineering ; Computer Science
  • É parte de: Journal of Computer and System Sciences, 2011, Vol.77(6), pp.1071-1078
  • Descrição: A tournament is a directed graph in which there is exactly one arc between every pair of distinct vertices. Given a digraph on vertices and an integer parameter , the problem asks whether the given digraph has a set of arcs whose removal results in an acyclic digraph. The problem restricted to tournaments is known as the - ( -FAST) problem. In this paper we obtain a linear vertex kernel for -FAST. That is, we give a polynomial time algorithm which given an input instance to -FAST obtains an equivalent instance on vertices. In fact, given any fixed , the kernelized instance has at most vertices. Our result improves the previous known bound of on the kernel size for -FAST. Our kernelization algorithm solves the problem on a subclass of tournaments in polynomial time and uses a known polynomial time approximation scheme for -FAST.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.