Parameterized complexity of the induced subgraph problem in directed graphs

DOI10.1016/J.IPL.2007.05.005MaRDI QIDQ2380001zbMATH OpenOpenAlexFDO

Authors Venkatesh Raman, Somnath Sikdar

Publication date 24 March 2010

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

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

zbMATH Keywords

computational complexityinduced subgraphdirected graphsparameterized complexitycombinatorial problemshereditary properties

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1696630
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized complexity of connected induced subgraph problems

Cites work

• scientific article; zbMATH DE number 3711961 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parametrized complexity theory.
• The node-deletion problem for hereditary properties is NP-complete

Cited in

(9)

• The Parameterized Complexity of k-Edge Induced Subgraphs
• scientific article; zbMATH DE number 1696630 (Why is no real title available?)
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of finding connected induced subgraphs
• Possible winner problems on partial tournaments: a parameterized study
• Parameterized complexity of Eulerian deletion problems
• Parameterized complexity of connected induced subgraph problems
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound

This page was built for publication: Parameterized complexity of the induced subgraph problem in directed graphs

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