scientific article; zbMATH DE number 7053390
From MaRDI portal
Publication:5743514
zbMath1421.68061MaRDI QIDQ5743514
Yngve Villanger, Fedor V. Fomin
Publication date: 10 May 2019
Full work available at URL: https://dl.acm.org/citation.cfm?id=2095254
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Minimum fill-in of sparse graphs: kernelization and approximation ⋮ Algorithms for automatic ranking of participants and tasks in an anonymized contest ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Faster parameterized algorithms for deletion to split graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Exact exponential algorithms.
- Faster parameterized algorithms for \textsc{Minimum Fill-in}
- On rigid circuit graphs
- Minimal triangulations of graphs: a survey
- A linear time algorithm to list the minimal separators of chordal graphs
- Approximating the Minimum Chain Completion problem
- Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
- Chordal completions of planar graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Which problems have strongly exponential complexity?
- Listing all potential maximal cliques of a graph
- A characterisation of rigid circuit graphs
- Incidence matrices and interval graphs
- Parametrized complexity theory.
- Treewidth and Minimum Fill-in: Grouping the Minimal Separators
- On the Desirability of Acyclic Database Schemes
- Finding Induced Subgraphs via Minimal Triangulations
- The Use of Linear Graphs in Gauss Elimination
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Direct Methods for Sparse Linear Systems
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Treewidth Computation and Extremal Combinatorics
- Exact Algorithms for Treewidth and Minimum Fill-In
- Fast FAST
- Interval Completion Is Fixed Parameter Tractable
- Computing the Minimum Fill-In is NP-Complete
- Triangulating 3-Colored Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
- Graph Sandwich Problems
- Two strikes against perfect phylogeny
- Computing Minimal Triangulations in Time O(nalpha log n) = o(n2.376)
