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
Title not available (Why is that?)
On computing large temporal (unilateral) connected components
Hypergraph edge elimination -- a symbolic phase for Hermitian eigensolvers based on rank-1 modifications
Bayesian networks: the minimal triangulations of a graph
Customizable contraction hierarchies
On 3-degree 4-chordal graphs
Graph classes and the switch Markov chain for matchings
Global minimization of polynomial integral functionals
The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
On tradeoffs between width- and fill-like graph parameters
Searching for better fill-in
Transmission operators for the non-overlapping Schwarz method for solving Helmholtz problems in rectangular cavities
Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work
A cubic-vertex kernel for flip consensus tree
Approximation algorithms in combinatorial scientific computing
Vertex deletion problems on chordal graphs
On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
A local reductive elimination for the fill-in of graphs
Bipartite completion of colored graphs avoiding chordless cycles of given lengths
Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
On computing large temporal (unilateral) connected components
Some completion problems for graphs without chordless cycles of prescribed lengths
Inference via low-dimensional couplings
All roads lead to Rome -- new search methods for the optimal triangulation problem
Decomposition of arithmetical np-hard problems
Recognizing sparse perfect elimination bipartite graphs
Minimum fill-in: inapproximability and almost tight lower bounds
On the minimum chordal completion polytope
Vertex deletion problems on chordal graphs
On the proper interval completion problem within some chordal subclasses
Learning chordal extensions
Vertex deletion on split graphs: beyond 4-hitting set
Minimum fill-in of sparse graphs: kernelization and approximation
Large-scale problems with quasi-block matrices
Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone
Seeing Arboretum for the (partial k-) Trees
Title not available (Why is that?)
Exploiting sparsity for the min \(k\)-partition problem
Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
A polynomial-time algorithm for outerplanar diameter improvement
Complexity of modification problems for best match graphs
Phyolin: identifying a linear perfect phylogeny in single-cell DNA sequencing data of tumors
Modification problems toward proper (Helly) circular-arc graphs
Generating weakly chordal graphs from arbitrary graphs
Triangulation Heuristics for BN2O Networks
On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
A polynomial-time algorithm for outerplanar diameter improvement
Permutation and Grouping Methods for Sharpening Gaussian Process Approximations

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)