Parameterized complexity of the induced subgraph problem in directed graphs

DOI10.1016/j.ipl.2007.05.005zbMath1185.05076OpenAlexW2078089071MaRDI QIDQ2380001

Somnath Sikdar, Venkatesh Raman

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 complexitycombinatorial problemsinduced subgraphdirected graphshereditary propertiesparameterized complexity

Mathematics Subject Classification ID

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

Related Items

Possible winner problems on partial tournaments: a parameterized study, Parameterized complexity of finding connected induced subgraphs, Parameterized complexity of Eulerian deletion problems, Parameterized Complexity of Eulerian Deletion Problems

Cites Work

• Parameterized algorithms for feedback set problems and their duals in tournaments
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parametrized complexity theory.
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item