Parameterized algorithms for even cycle transversal

DOI10.1007/978-3-642-34611-8_19MaRDI QIDQ5200504zbMATH OpenOpenAlexFDO

Authors Pranabendu Misra, Venkatesh Raman, M. S. Ramanujan, Saket Saurabh

Publication date 6 November 2012

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-34611-8_19

zbMATH Keywords

odd cycle transversal problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Transversal (matching) theory (05D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• On polynomial kernels for structural parameterizations of odd cycle transversal
• Faster graph bipartization
• Parameterized complexity of even/odd subgraph problems
• Parameterized complexity of even/odd subgraph problems
• scientific article; zbMATH DE number 6297714

Cited in

(19)

• (In)approximability of maximum minimal FVS
• Faster deterministic algorithm for cactus vertex deletion
• An improved deterministic parameterized algorithm for cactus vertex deletion
• Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs
• Backdoors to tractable answer set programming
• Fixed-parameter tractability for subset feedback set problems with parity constraints
• Quick but odd growth of cacti
• On polynomial kernels for structural parameterizations of odd cycle transversal
• Parameterized approximations via d-skew-symmetric multicut
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• Parameterized Algorithms for List K-Cycle
• Exploring the kernelization borders for hitting cycles
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Hitting weighted even cycles in planar graphs
• scientific article; zbMATH DE number 6297714 (Why is no real title available?)
• Computing subset transversals in \(H\)-free graphs
• Constrained Hitting Set and Steiner Tree in SCk and 2K2-free Graphs
• Tree decompositions meet induced matchings: beyond max weight independent set
• Tree decompositions meet induced matchings: beyond max weight independent set

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Parameterized algorithms for even cycle transversal

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