Structural parameterizations with modulator oblivion

DOI10.4230/LIPICS.IPEC.2020.19MaRDI QIDQ6089666zbMATH OpenFDO

Authors Ashwin Jacob, Fahad Panolan, Venkatesh Raman, Vibha Sahlot

Publication date 13 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2020.19

zbMATH Keywords

chordal graphparameterized complexitystrong exponential time hypothesistree decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Recommendations

• Structural parameterizations with modulator oblivion
• Chordal deletion is fixed-parameter tractable
• Chordal Deletion Is Fixed-Parameter Tractable
• Approximation and kernelization for chordal vertex deletion

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A simple linear time algorithm for cograph recognition
• Algorithm Theory - SWAT 2004
• Algorithmic graph theory and perfect graphs
• Approximation and kernelization for chordal vertex deletion
• Backdoors to satisfaction
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Chordal editing is fixed-parameter tractable
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Dominating Sets in Chordal Graphs
• Efficient graph representations
• Erdős-Pósa property of chordless cycles and its applications
• Faster parameterized algorithms using linear programming
• Functional analysis
• Fundamentals of parameterized complexity
• Graph minors. XIII: The disjoint paths problem
• Graph theory
• scientific article; zbMATH DE number 1839471 (Why is no real title available?)
• Large Induced Subgraphs via Triangulations and CMSO
• On problems as hard as CNF-SAT
• Parameterized algorithms
• Parameterized complexity of vertex deletion into perfect graph classes
• Parameterized single-exponential time polynomial space algorithm for Steiner tree
• Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Robust algorithms for restricted domains
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• The complexity of generalized clique covering
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Unit disk graph recognition is NP-hard
• Unit disk graphs
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter

Cited in

(4)

• Structural parameterizations with modulator oblivion
• ArbiLoMod, a Simulation Technique Designed for Arbitrary Local Modifications
• Kernelization for feedback vertex set via elimination distance to a forest
• Tight bounds for chordal/interval vertex deletion parameterized by treewidth

This page was built for publication: Structural parameterizations with modulator oblivion

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