When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices

MaRDI QIDQ4608015zbMATH OpenFDO

Authors Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175430

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Parameterised algorithms for deletion to classes of DAGs
• Polynomial kernels for deletion to classes of acyclic digraphs
• Computing and Combinatorics
• Tight Bounds for the Maximum Acyclic Subgraph Problem

Cited in

(7)

• scientific article; zbMATH DE number 7559446 (Why is no real title available?)
• Parameterized algorithms for generalizations of directed feedback vertex set
• On Weighted Graph Separation Problems and Flow Augmentation
• Recognizing when a preference system is close to admitting a master list
• On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components
• Odd multiway cut in directed acyclic graphs
• Recognizing when a preference system is close to admitting a master list

This page was built for publication: When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices

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