scientific article; zbMATH DE number 7278081

DOI10.4230/LIPICS.FSTTCS.2017.9MaRDI QIDQ5136298zbMATH OpenFDO

Authors Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, M. S. Ramanujan

Publication date 25 November 2020

zbMATH Keywords

parameterized complexityfeedback vertex setedge-colored graphsodd cycle transversalsimultaneous deletion

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of Eulerian deletion problems
• On the complexity of bounded deletion propagation
• Parameterized complexity of deletion to scattered graph classes
• Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
• The complexity of deletion problems for matroids
• The complexity of some edge deletion problems
• A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

Cites work

• scientific article; zbMATH DE number 1222098 (Why is no real title available?)
• A near-optimal planarization algorithm
• Chordal editing is fixed-parameter tractable
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Discovering archipelagos of tractability for constraint satisfaction and counting
• Dual connectedness of edge-bicolored graphs and beyond
• Faster deterministic \textsc{Feedback Vertex Set}
• Faster parameterized algorithms using linear programming
• Finding odd cycle transversals.
• Finding small separators in linear time via treewidth reduction
• Improved algorithms for feedback vertex set problems
• Improved upper bounds for vertex cover
• Interval deletion is fixed-parameter tractable
• Linear time parameterized algorithms for subset feedback vertex set
• Linear time parameterized algorithms via skew-symmetric multicuts
• Linear-time FPT algorithms via network flow
• Parameterized algorithms
• Parameterized tractability of multiway cut with parity constraints
• Simultaneous feedback vertex set: a parameterized perspective

Cited in

(7)

• Simultaneous feedback vertex set: a parameterized perspective
• Simultaneous feedback vertex set: a parameterized perspective
• Simultaneous feedback edge set: a parameterized perspective
• Strong parameterized deletion: bipartite graphs
• scientific article; zbMATH DE number 1763413 (Why is no real title available?)
• Simultaneous feedback edge set: a parameterized perspective
• Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136298)