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

zbMATH Open1403.68170MaRDI QIDQ4608015FDOQ4608015

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

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

Mathematics Subject Classification ID

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

Cited In (7)

• Title not available (Why is that?)
• 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
• Recognizing when a preference system is close to admitting a master list
• Odd multiway cut in directed acyclic graphs

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)