Computing the Minimum Fill-In is NP-Complete

Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

Title not available (Why is that?)
Some simplified NP-complete graph problems
Node-Deletion Problems on Bipartite Graphs
Algorithmic Aspects of Vertex Elimination on Graphs
Title not available (Why is that?)
Algorithmic Aspects of Vertex Elimination on Directed Graphs

Cited In (only showing first 100 items - show all)

An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
Polynomial kernels for proper interval completion and related problems
How to use the minimal separators of a graph for its chordal triangulation
Chordal decomposition in operator-splitting methods for sparse semidefinite programs
On sparse matrix orderings in interior point methods
Title not available (Why is that?)
Graphical models for genetic analyses
Title not available (Why is that?)
Treewidth and minimum fill-in on permutation graphs in linear time
A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
On the ordering of sparse linear systems
Minimal split completions
NP-completeness results for edge modification problems
The graph sandwich problem for \(P_4\)-sparse graphs
A Separator Theorem for Chordal Graphs
Algorithms and complexity of sandwich problems in graphs (extended abstract)
Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
Edge deletion problems: branching facilitated by modular decomposition
A vertex incremental approach for maintaining chordality
Characterizations and algorithmic applications of chordal graph embeddings
On treewidth and minimum fill-in of asteroidal triple-free graphs
Proper interval vertex deletion
Discovering a junction tree behind a Markov network by a greedy algorithm
Exploiting special structure in semidefinite programming: a survey of theory and applications
Decomposition by clique separators
Fixed-parameter tractability of graph modification problems for hereditary properties
The complexity of reconstructing trees from qualitative characters and subtrees
Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
The homogeneous set sandwich problem
Chordal editing is fixed-parameter tractable
Triangulating graphs without asteroidal triples
Minimal triangulations of graphs: a survey
An implementation of Karmarkar's algorithm for linear programming
A practical algorithm for making filled graphs minimal
Decomposing constraint satisfaction problems using database techniques
Near-optimal solutions for the generalized max-controlled set problem
An introduction to clique minimal separator decomposition
Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
Bipartite permutation graphs
Fast minimal triangulation algorithm using minimum degree criterion
Characterizing and Computing Minimal Cograph Completions
On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
Complexity classification of some edge modification problems
Subexponential parameterized algorithms and kernelization on almost chordal graphs
Chordal deletion is fixed-parameter tractable
Minimal comparability completions of arbitrary graphs
Maximal chordal subgraphs
Planar disjoint-paths completion
Graphs with maximal induced matchings of the same size
A triangulation and fill-reducing initialization procedure for the simplex algorithm
Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
Finding minimum height elimination trees for interval graphs in polynomial time
Efficient Adaptive MCMC Through Precision Estimation
NP-hard graph problems and boundary classes of graphs
Triangulating multitolerance graphs
Decision Diagram Decomposition for Quadratically Constrained Binary Optimization
Listing all potential maximal cliques of a graph
Independent sets in asteroidal triple-free graphs
Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
PMORSy: parallel sparse matrix ordering software for fill-in minimization
Planar disjoint-paths completion
Domination and total domination on asteroidal triple-free graphs
Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
Graph modification problem for some classes of graphs
A direct active set algorithm for large sparse quadratic programs with simple bounds
Coreduction homology algorithm
Strongly chordal and chordal bipartite graphs are sandwich monotone
Faster parameterized algorithms for \textsc{Minimum Fill-in}
Complexity of Finding Embeddings in a k-Tree
Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
On sum coloring of graphs
Cooperative triangulation in MSBNs without revealing subnet structures
Linear time optimization algorithms for \(P_ 4\)-sparse graphs
Optimal labelling of unit interval graphs
The analysis of a nested dissection algorithm
The Complexity of the Partial Order Dimension Problem
An implementation of the iterative proportional fitting procedure by propagation trees.
Estimating spatial covariance using penalised likelihood with weightedL₁penalty
A Subexponential Parameterized Algorithm for Proper Interval Completion
Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming
Solving quadratically constrained convex optimization problems with an interior-point method
Minimal elimination ordering for graphs of bounded degree
A linear time algorithm to list the minimal separators of chordal graphs
Lex M versus MCS-M
Efficient solutions of hierarchical systems of linear equations
Decomposition methods for sparse matrix nearness problems
A survey of direct methods for sparse linear systems
Characterizing and computing minimal cograph completions
Parameterized enumeration for modification problems
Tree decomposition and discrete optimization problems: a survey
A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
Hardness results and an exact exponential algorithm for the spanning tree congestion problem
Linear optimization over homogeneous matrix cones
On listing, sampling, and counting the chordal graphs with edge constraints
Parallelized integrated nested Laplace approximations for fast Bayesian inference
An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem

This page was built for publication: Computing the Minimum Fill-In is NP-Complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3960122)