Parameterized algorithms for feedback vertex set

DOI10.1007/978-3-540-28639-4_21MaRDI QIDQ5311516zbMATH OpenOpenAlexFDO

Authors Michael J. Pelsmajer, Marcus Schaefer, Iyad Kanj

Publication date 23 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100584

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Improved Algorithms for the Feedback Vertex Set Problems
• Improved algorithms for feedback vertex set problems
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Faster fixed parameter tractable algorithms for undirected feedback vertex set
• On feedback vertex set new measure and new structures

Cited in

(40)

• On directed feedback vertex set parameterized by treewidth
• Feedback vertex set on graphs of low clique-width
• Faster deterministic \textsc{Feedback Vertex Set}
• On the complexity of singly connected vertex deletion
• Mim-width. II. The feedback vertex set problem
• A polynomial kernel for block graph deletion
• An improved parameterized algorithm for the independent feedback vertex set problem
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• Deterministic Algorithms for the Independent Feedback Vertex Set Problem
• A quartic kernel for pathwidth-one vertex deletion
• A unified polynomial-time algorithm for feedback vertex set on graphs of bounded mim-width
• FPT algorithms for connected feedback vertex set
• A fixed-parameter algorithm for the directed feedback vertex set problem
• A Linear Kernel for Planar Feedback Vertex Set
• On feedback vertex set new measure and new structures
• Improved Algorithms for the Feedback Vertex Set Problems
• Feedback vertex set on graphs of low cliquewidth
• Faster fixed parameter tractable algorithms for undirected feedback vertex set
• FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
• Structural Parameterizations of Feedback Vertex Set
• A polyhedral approach to the feedback vertex set problem
• On feedback vertex set: new measure and new structures
• On the Complexity of Singly Connected Vertex Deletion
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• A naive algorithm for feedback vertex set
• Algorithms and Data Structures
• scientific article; zbMATH DE number 970357 (Why is no real title available?)
• Computing and Combinatorics
• An improved FPT algorithm for independent feedback vertex set
• Detecting Feedback Vertex Sets of Size k in O ^⋆ (2.7 k ) Time
• A parameterized algorithm for subset feedback vertex set in tournaments
• On parameterized independent feedback vertex set
• FPT algorithms for connected feedback vertex set
• Solving subset feedback vertex set in chordal graphs faster than 2ᵏ
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• A cubic kernel for feedback vertex set and loop cutset

This page was built for publication: Parameterized algorithms for feedback vertex set

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