Subexponential parameterized algorithms and kernelization on almost chordal graphs
type: Item
instance of: scholarly article
title: Subexponential parameterized algorithms and kernelization on almost chordal graphs
zbMATH Open document ID: 1467.05254
author: Fedor V. Fomin
author: Petr A. Golovach
published in: Algorithmica
publication date: 2021-06-30T00:00:00Z
full work available at URL: https://arxiv.org/abs/2002.08226
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 7365274
zbMATH Keywords: parameterized complexity
zbMATH Keywords: structural parameterization
zbMATH Keywords: subexponential algorithms
zbMATH Keywords: kernelization
zbMATH Keywords: chordal graphs
zbMATH Keywords: fill-in
zbMATH Keywords: independent set
zbMATH Keywords: clique
zbMATH Keywords: coloring
MaRDI profile type: Publication
OpenAlex ID: W3082325482
arXiv ID: 2002.08226
cites work: Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
cites work: Interval Vertex Deletion Admits a Polynomial Kernel
cites work: A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
cites work: Polynomial kernels for proper interval completion and related problems
cites work: Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp>
cites work: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
cites work: Faster parameterized algorithms for \textsc{Minimum Fill-in}
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: Graph Classes: A Survey
cites work: A characterisation of rigid circuit graphs
cites work: Fixed-parameter tractability of graph modification problems for hereditary properties
cites work: Parameterized complexity of vertex colouring
cites work: Linear Recognition of Almost Interval Graphs
cites work: Unit interval editing is fixed-parameter tractable
cites work: Interval Deletion Is Fixed-Parameter Tractable
cites work: Minimum fill-in: inapproximability and almost tight lower bounds
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Parameterized Algorithms
cites work: Fast Hamiltonicity Checking Via Bases of Perfect Matchings
cites work: Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
cites work: Fundamentals of parameterized complexity
cites work: On chromatic number of graphs and set-systems
cites work: Polynomial kernels for weighted problems
cites work: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
cites work: Kernelization
cites work: A Polynomial Kernel for Proper Interval Vertex Deletion
cites work: Large Induced Subgraphs via Triangulations and CMSO
cites work: Subexponential Parameterized Algorithm for Minimum Fill-In
cites work: An application of simultaneous diophantine approximation in combinatorial optimization
cites work: Q4198056
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Algorithms on circular-arc graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Geometric algorithms and combinatorial optimization.
cites work: The splittance of a graph
cites work: Minimal triangulations of graphs: a survey
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Data reduction for graph coloring problems
cites work: Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
cites work: Approximation and Kernelization for Chordal Vertex Deletion
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: Cluster editing with locally bounded modifications
cites work: Representation of a finite graph by a set of intervals on the real line
cites work: Beyond classes of graphs with ``few'' minimal separators: FPT results through potential maximal cliques
cites work: Parameterized coloring problems on chordal graphs
cites work: Chordal deletion is fixed-parameter tractable
cites work: Smallest-last ordering and clustering and graph coloring algorithms
cites work: Q4542518
cites work: Complexity classification of some edge modification problems
cites work: Sparsity. Graphs, structures, and algorithms
cites work: The Use of Linear Graphs in Gauss Elimination
cites work: Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
cites work: New Approximation Techniques for Some Linear Ordering Problems

Subexponential parameterized algorithms and kernelization on almost chordal graphs (cites work)
cites work: Q5683627

Subexponential parameterized algorithms and kernelization on almost chordal graphs (cites work)
cites work: Algorithmic Aspects of Vertex Elimination on Graphs

Subexponential parameterized algorithms and kernelization on almost chordal graphs (cites work)
cites work: Vertex Coloring of Comparability+ke and –ke Graphs

Subexponential parameterized algorithms and kernelization on almost chordal graphs (cites work)
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Subexponential parameterized algorithms and kernelization on almost chordal graphs (cites work)
cites work: Interval Completion Is Fixed Parameter Tractable

Subexponential parameterized algorithms and kernelization on almost chordal graphs (cites work)
cites work: Computing the Minimum Fill-In is NP-Complete

Subexponential parameterized algorithms and kernelization on almost chordal graphs (DOI)
DOI: 10.1007/S00453-021-00822-X