scientific article; zbMATH DE number 7651188
From MaRDI portal
Publication:5874519
DOI10.4230/LIPIcs.ESA.2020.49MaRDI QIDQ5874519
Fedor V. Fomin, Petr A. Golovach
Publication date: 7 February 2023
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
independent setcliquechordal graphscoloringfill-inparameterized complexitykernelizationstructural parameterizationsubexponential algorithms
Cites Work
- 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
- Minimal triangulations of graphs: a survey
- Parameterized coloring problems on chordal graphs
- Chordal deletion is fixed-parameter tractable
- Finding Hamiltonian circuits in interval graphs
- 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
- 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
- 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
- Computing the Minimum Fill-In is NP-Complete
- 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
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Complexity classification of some edge modification problems
This page was built for publication:
