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)

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
Algebras for tree decomposable graphs
Approximating the Minimum Chain Completion problem
Parikh word representability of bipartite permutation graphs
Title not available (Why is that?)
The General Minimum Fill-In Problem
Computing Tree Decompositions
Minimal separators in extended \(P_4\)-laden graphs
Decomposition in multidimensional Boolean-optimization problems with sparse matrices
A survey of parameterized algorithms and the complexity of edge modification
Computational aspects of DNA mixture analysis
Robustness to dependency in portfolio optimization using overlapping marginals
On the interval completion of chordal graphs
The isomorphic version of Brualdi's and Sanderson's nestedness
Solution methods for the vertex variant of the network system vulnerability analysis problem
Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
Parallel sparse Gaussian elimination with partial pivoting
An appraisal of computational complexity for operations researchers
A note on fast approximate minimum degree orderings for symmetric matrices with some dense rows
Title not available (Why is that?)
Wheel-Free Deletion Is W[2]-Hard
Efficiently enumerating minimal triangulations
On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
The average parallel complexity of Cholesky factorization
Exploring the subexponential complexity of completion problems
Solution of sparse positive definite systems on a hypercube
Distance descending ordering method: an \(O(n)\) algorithm for inverting the mass matrix in simulation of macromolecules with long branches
Minimal elimination of planar graphs
Triangulating graphs with few \(P_4\)'s
Updating credal networks is approximable in polynomial time
Digraphs of bounded elimination width
QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
Efficient function approximation on general bounded domains using splines on a Cartesian grid
Pathwidth is NP-Hard for Weighted Trees
\(K_{1,3}\)-free and \(W_4\)-free graphs
An \(O(n^2)\) time algorithm for the minimal permutation completion problem
Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
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

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)