An FPT algorithm for edge subset feedback edge set

DOI10.1016/J.IPL.2011.10.007MaRDI QIDQ763477zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 9 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2011.10.007

zbMATH Keywords

graph algorithmsfixed-parameter tractablefeedback setedge feedback set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Algorithms and Data Structures
• Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
• Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}

Cites work

• scientific article; zbMATH DE number 571325 (Why is no real title available?)
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• A fixed-parameter algorithm for the directed feedback vertex set problem
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Approximating minimum feedback sets and multicuts in directed graphs
• Improved algorithms for feedback vertex set problems
• Simple and improved parameterized algorithms for multiterminal cuts

Cited in

(8)

• FPT algorithms for connected feedback vertex set
• scientific article; zbMATH DE number 7561552 (Why is no real title available?)
• Covering Vectors by Spaces: Regular Matroids
• A survey of parameterized algorithms and the complexity of edge modification
• Finding a Nonempty Algebraic Subset of an Edge Set in Linear Time
• Simultaneous feedback edge set: a parameterized perspective
• Feedback edge sets in temporal graphs
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth

This page was built for publication: An FPT algorithm for edge subset feedback edge set

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