Parameterized Eulerian strong component arc deletion problem on tournaments

R. Crowston; G. Gutin; M. Jones; A. Yeo

doi:10.1016/j.ipl.2011.11.014

Parameterized Eulerian strong component arc deletion problem on tournaments

R. Crowston
, G. Gutin
, M. Jones
, A. Yeo

Royal Holloway University of London

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

In the problem Min-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A′ of at most k arcs in D, such that if we remove the arcs of A′, in the resulting digraph every strong component is Eulerian. Min-DESC is NP-hard; Cechlárová and Schlotter (IPEC 2010) asked whether the problem is fixed-parameter tractable when parameterized by k. We consider the subproblem of Min-DESC when D is a tournament. We show that this problem is fixed-parameter tractable with respect to k.

Original language	English
Pages (from-to)	249-251
Number of pages	3
Journal	Information Processing Letters
Volume	112
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2011.11.014
Publication status	Published - 15 Mar 2012
Externally published	Yes

Keywords

Design of algorithms
Eulerian digraphs
Fixed-parameter tractability
Graph algorithms
Tournaments

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/j.ipl.2011.11.014

Cite this

@article{d8fe2ba3e1434d45a8766745526bc196,

title = "Parameterized Eulerian strong component arc deletion problem on tournaments",

abstract = "In the problem Min-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A′ of at most k arcs in D, such that if we remove the arcs of A′, in the resulting digraph every strong component is Eulerian. Min-DESC is NP-hard; Cechl{\'a}rov{\'a} and Schlotter (IPEC 2010) asked whether the problem is fixed-parameter tractable when parameterized by k. We consider the subproblem of Min-DESC when D is a tournament. We show that this problem is fixed-parameter tractable with respect to k.",

keywords = "Design of algorithms, Eulerian digraphs, Fixed-parameter tractability, Graph algorithms, Tournaments",

author = "R. Crowston and G. Gutin and M. Jones and A. Yeo",

year = "2012",

month = mar,

day = "15",

doi = "10.1016/j.ipl.2011.11.014",

language = "English",

volume = "112",

pages = "249--251",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "6",

}

TY - JOUR

T1 - Parameterized Eulerian strong component arc deletion problem on tournaments

AU - Crowston, R.

AU - Gutin, G.

AU - Jones, M.

AU - Yeo, A.

PY - 2012/3/15

Y1 - 2012/3/15

N2 - In the problem Min-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A′ of at most k arcs in D, such that if we remove the arcs of A′, in the resulting digraph every strong component is Eulerian. Min-DESC is NP-hard; Cechlárová and Schlotter (IPEC 2010) asked whether the problem is fixed-parameter tractable when parameterized by k. We consider the subproblem of Min-DESC when D is a tournament. We show that this problem is fixed-parameter tractable with respect to k.

AB - In the problem Min-DESC, we are given a digraph D and an integer k, and asked whether there exists a set A′ of at most k arcs in D, such that if we remove the arcs of A′, in the resulting digraph every strong component is Eulerian. Min-DESC is NP-hard; Cechlárová and Schlotter (IPEC 2010) asked whether the problem is fixed-parameter tractable when parameterized by k. We consider the subproblem of Min-DESC when D is a tournament. We show that this problem is fixed-parameter tractable with respect to k.

KW - Design of algorithms

KW - Eulerian digraphs

KW - Fixed-parameter tractability

KW - Graph algorithms

KW - Tournaments

UR - https://www.scopus.com/pages/publications/84855459766

U2 - 10.1016/j.ipl.2011.11.014

DO - 10.1016/j.ipl.2011.11.014

M3 - Article

AN - SCOPUS:84855459766

SN - 0020-0190

VL - 112

SP - 249

EP - 251

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Parameterized Eulerian strong component arc deletion problem on tournaments

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this