Subexponential parameterized algorithms and kernelization on almost chordal graphs
From MaRDI portal
Publication:2037110
DOI10.1007/S00453-021-00822-XzbMath1467.05254arXiv2002.08226OpenAlexW3082325482MaRDI QIDQ2037110
Fedor V. Fomin, Petr A. Golovach
Publication date: 30 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2002.08226
independent setcliquechordal graphscoloringfill-inparameterized complexitykernelizationstructural parameterizationsubexponential algorithms
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (3)
Structural parameterizations with modulator oblivion ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Treewidth versus clique number. II: Tree-independence number
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial kernels for weighted problems
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- Data reduction for graph coloring problems
- Polynomial kernels for proper interval completion and related problems
- Sparsity. Graphs, structures, and algorithms
- Unit interval editing is fixed-parameter tractable
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Cluster editing with locally bounded modifications
- Minimal triangulations of graphs: a survey
- Parameterized coloring problems on chordal graphs
- Chordal deletion is fixed-parameter tractable
- An application of simultaneous diophantine approximation in combinatorial optimization
- The splittance of a graph
- Geometric algorithms and combinatorial optimization.
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Which problems have strongly exponential complexity?
- Parameterized complexity of vertex colouring
- A characterisation of rigid circuit graphs
- Minimum fill-in: inapproximability and almost tight lower bounds
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Large Induced Subgraphs via Triangulations and CMSO
- Problems Parameterized by Treewidth Tractable in Single Exponential Time: A Logical Approach
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- The Use of Linear Graphs in Gauss Elimination
- Representation of a finite graph by a set of intervals on the real line
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Vertex Coloring of Comparability+ke and –ke Graphs
- Interval Completion Is Fixed Parameter Tractable
- Smallest-last ordering and clustering and graph coloring algorithms
- Computing the Minimum Fill-In is NP-Complete
- Algorithms on circular-arc graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Graph Classes: A Survey
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Subexponential Parameterized Algorithm for I <scp>nterval</scp> C <scp>ompletion</scp>
- Fast Hamiltonicity Checking Via Bases of Perfect Matchings
- Linear Recognition of Almost Interval Graphs
- Approximation and Kernelization for Chordal Vertex Deletion
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Kernelization
- New Approximation Techniques for Some Linear Ordering Problems
- Interval Deletion Is Fixed-Parameter Tractable
- Kernelization Lower Bounds by Cross-Composition
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- Interval Vertex Deletion Admits a Polynomial Kernel
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- On chromatic number of graphs and set-systems
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- On the complexity of \(k\)-SAT
- Complexity classification of some edge modification problems
This page was built for publication: Subexponential parameterized algorithms and kernelization on almost chordal graphs
