scientific article; zbMATH DE number 7764110

DOI10.4230/lipics.ipec.2020.19MaRDI QIDQ6089666

Venkatesh Raman, Fahad Panolan, Vibha Sahlot, Ashwin Jacob

Publication date: 13 November 2023

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

tree decompositionchordal graphparameterized complexitystrong exponential time hypothesis

Mathematics Subject Classification ID

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

Related Items

Structural parameterizations with modulator oblivion, Kernelization for feedback vertex set via elimination distance to a forest

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordal editing is fixed-parameter tractable
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Fundamentals of parameterized complexity
• Parameterized complexity of vertex deletion into perfect graph classes
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• Unit disk graphs
• The complexity of generalized clique covering
• Unit disk graph recognition is NP-hard
• Efficient graph representations
• A simple linear time algorithm for cograph recognition
• Algorithmic graph theory and perfect graphs
• Graph minors. XIII: The disjoint paths problem
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Polynomial kernels for vertex cover parameterized by small degree modulators
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• On Multiway Cut Parameterized above Lower Bounds
• Backdoors to Satisfaction
• Large Induced Subgraphs via Triangulations and CMSO
• Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree
• Dominating Sets in Chordal Graphs
• Robust algorithms for restricted domains
• Approximation and Kernelization for Chordal Vertex Deletion
• Erd\H{o}s-P\'osa property of chordless cycles and its applications
• Faster Parameterized Algorithms Using Linear Programming
• On Problems as Hard as CNF-SAT
• Algorithm Theory - SWAT 2004
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Functional analysis