scientific article; zbMATH DE number 7378606
From MaRDI portal
Publication:5009483
DOI10.4230/LIPIcs.IPEC.2018.20MaRDI QIDQ5009483
Charis Papadopoulos, Spyridon Tzimas
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1805.07141
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
NP-completenesspolynomial-time algorithmW[1-hardness]subset feedback vertex setnode multiway cutgraphs of bounded indeterminal set problem
Related Items (1)
Cites Work
- Unnamed Item
- Fundamentals of parameterized complexity
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Enumerating minimal subset feedback vertex sets
- Parameterized graph separation problems
- Feedback vertex set on AT-free graphs
- On the parameterized complexity of multiple-interval graph problems
- The complexity of generalized clique covering
- Efficient graph representations
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Algorithmic graph theory and perfect graphs
- Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
- Feedback vertex set on graphs of low clique-width
- Faster exact algorithms for some terminal set problems
- An improved parameterized algorithm for the minimum node multiway cut problem
- Subset feedback vertex sets in chordal graphs
- Faster Exact Algorithms for Some Terminal Set Problems
- On Multiway Cut Parameterized above Lower Bounds
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Node-Deletion Problems on Bipartite Graphs
- Graph Classes: A Survey
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Multiway cuts in node weighted graphs
- Exact Algorithms via Monotone Local Search
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Max flows in O(nm) time, or better
- Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs
This page was built for publication:
