Computing the Minimum Fill-In is NP-Complete
From MaRDI portal
Publication:3960122
DOI10.1137/0602010zbMath0496.68033OpenAlexW2027566319MaRDI QIDQ3960122
Publication date: 1981
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/8561d23058501c8f2c245bffb3001e488192a7a3
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, A linear time algorithm to list the minimal separators of chordal graphs, Lex M versus MCS-M, The homogeneous set sandwich problem, Efficient solutions of hierarchical systems of linear equations, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Chordal editing is fixed-parameter tractable, Bipartite permutation graphs, On Dasgupta's hierarchical clustering objective and its relation to other graph parameters, Finding minimum height elimination trees for interval graphs in polynomial time, Fixed-parameter tractability of graph modification problems for hereditary properties, Bipartite completion of colored graphs avoiding chordless cycles of given lengths, Linear time optimization algorithms for \(P_ 4\)-sparse graphs, Towards constant-factor approximation for chordal/distance-hereditary vertex deletion, The analysis of a nested dissection algorithm, Planar disjoint-paths completion, Decomposition in multidimensional Boolean-optimization problems with sparse matrices, Optimal labelling of unit interval graphs, Graphs with maximal induced matchings of the same size, The isomorphic version of Brualdi's and Sanderson's nestedness, Graph modification problem for some classes of graphs, A local reductive elimination for the fill-in of graphs, Maximal chordal subgraphs, An introduction to clique minimal separator decomposition, Characterizations and algorithmic applications of chordal graph embeddings, Triangulating graphs without asteroidal triples, Solution of sparse positive definite systems on a hypercube, Exploiting sparsity for the min \(k\)-partition problem, On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}, An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem, Polynomial kernels for proper interval completion and related problems, Parikh word representability of bipartite permutation graphs, On treewidth and minimum fill-in of asteroidal triple-free graphs, Triangulating multitolerance graphs, Discovering a junction tree behind a Markov network by a greedy algorithm, On sparse matrix orderings in interior point methods, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, Distance descending ordering method: an \(O(n)\) algorithm for inverting the mass matrix in simulation of macromolecules with long branches, Proper interval vertex deletion, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, Domination and total domination on asteroidal triple-free graphs, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, An \(O(n^2)\) time algorithm for the minimal permutation completion problem, Faster parameterized algorithms for \textsc{Minimum Fill-in}, Hypergraph edge elimination -- a symbolic phase for Hermitian eigensolvers based on rank-1 modifications, Strongly chordal and chordal bipartite graphs are sandwich monotone, An appraisal of computational complexity for operations researchers, COSMO: a conic operator splitting method for convex conic problems, \(K_{1,3}\)-free and \(W_4\)-free graphs, Efficiently enumerating minimal triangulations, The average parallel complexity of Cholesky factorization, Unit interval editing is fixed-parameter tractable, Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming, The complexity of reconstructing trees from qualitative characters and subtrees, On tradeoffs between width- and fill-like graph parameters, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Minimal separators in extended \(P_4\)-laden graphs, Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts, Edge deletion problems: branching facilitated by modular decomposition, Minimal split completions, Minimum fill-in of sparse graphs: kernelization and approximation, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Graphical models for genetic analyses, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Characterizing and computing minimal cograph completions, Chordal deletion is fixed-parameter tractable, Fast minimal triangulation algorithm using minimum degree criterion, A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods, On listing, sampling, and counting the chordal graphs with edge constraints, Near-optimal solutions for the generalized max-controlled set problem, Treewidth and minimum fill-in on permutation graphs in linear time, Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network, Solution methods for the vertex variant of the network system vulnerability analysis problem, Algorithms for automatic ranking of participants and tasks in an anonymized contest, Some completion problems for graphs without chordless cycles of prescribed lengths, Approximating the Minimum Chain Completion problem, A direct active set algorithm for large sparse quadratic programs with simple bounds, Vertex deletion problems on chordal graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Large-scale problems with quasi-block matrices, Coreduction homology algorithm, Learning chordal extensions, On the threshold of intractability, On sum coloring of graphs, Parallel sparse Gaussian elimination with partial pivoting, A triangulation and fill-reducing initialization procedure for the simplex algorithm, The graph sandwich problem for \(P_4\)-sparse graphs, An implementation of Karmarkar's algorithm for linear programming, Triangulating graphs with few \(P_4\)'s, Exploiting special structure in semidefinite programming: a survey of theory and applications, QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs, Efficient function approximation on general bounded domains using splines on a Cartesian grid, A practical algorithm for making filled graphs minimal, Decomposition by clique separators, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, Listing all potential maximal cliques of a graph, An implementation of the iterative proportional fitting procedure by propagation trees., Decomposing constraint satisfaction problems using database techniques, Planar Disjoint-Paths Completion, Seeing Arboretum for the (partial k-) Trees, Computing Tree Decompositions, Updating credal networks is approximable in polynomial time, All roads lead to Rome -- new search methods for the optimal triangulation problem, Unnamed Item, Minimal elimination of planar graphs, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Decomposition Methods for Sparse Matrix Nearness Problems, Estimating spatial covariance using penalised likelihood with weightedL1penalty, Graphical Models and Message-Passing Algorithms: Some Introductory Lectures, Exactly Solving Sparse Rational Linear Systems via Roundoff-Error-Free Cholesky Factorizations, A Polynomial-Time Algorithm for Outerplanar Diameter Improvement, Pathwidth is NP-Hard for Weighted Trees, Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, A polynomial-time algorithm for outerplanar diameter improvement, Independent sets in asteroidal triple-free graphs, Complexity of modification problems for best match graphs, Complexity of Finding Embeddings in a k-Tree, Completion to chordal distance-hereditary graphs: a quartic vertex-kernel, Algebras for Tree Decomposable Graphs, Linear optimization over homogeneous matrix cones, Parallelized integrated nested Laplace approximations for fast Bayesian inference, Wheel-Free Deletion Is W[2-Hard], Automating algorithm selection: checking for matrix properties that can simplify computations, Generating weakly chordal graphs from arbitrary graphs, Decomposition of arithmetical np-hard problems, Characterizing and Computing Minimal Cograph Completions, Unnamed Item, A survey of parameterized algorithms and the complexity of edge modification, Transmission operators for the non-overlapping Schwarz method for solving Helmholtz problems in rectangular cavities, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Unnamed Item, On 3-degree 4-chordal graphs, On computing large temporal (unilateral) connected components, Algorithms and complexity of sandwich problems in graphs (extended abstract), A cubic vertex-kernel for \textsc{Trivially Perfect Editing}, Unnamed Item, A cubic-vertex kernel for flip consensus tree, Digraphs of bounded elimination width, The General Minimum Fill-In Problem, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Searching for better fill-in, Recognizing Sparse Perfect Elimination Bipartite Graphs, NP-hard graph problems and boundary classes of graphs, How to use the minimal separators of a graph for its chordal triangulation, Minimal comparability completions of arbitrary graphs, Unnamed Item, Tree decomposition and discrete optimization problems: a survey, Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation, A survey of direct methods for sparse linear systems, On the ordering of sparse linear systems, On the interval completion of chordal graphs, A Separator Theorem for Chordal Graphs, Complexity classification of some edge modification problems, NP-completeness results for edge modification problems, Minimal elimination ordering for graphs of bounded degree, An improved derandomized approximation algorithm for the max-controlled set problem, Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals, Parameterized Enumeration for Modification Problems, Graph classes and the switch Markov chain for matchings, Computational aspects of DNA mixture analysis, Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem, Unnamed Item, Approximation Algorithms for Minimum Chain Vertex Deletion, Vertex deletion on split graphs: beyond 4-hitting set, Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results, A Subexponential Parameterized Algorithm for Proper Interval Completion, Minimum fill-in: inapproximability and almost tight lower bounds, Polynomial Kernels for Proper Interval Completion and Related Problems, A note on fast approximate minimum degree orderings for symmetric matrices with some dense rows, Efficient Adaptive MCMC Through Precision Estimation, Triangulation Heuristics for BN2O Networks, Solving quadratically constrained convex optimization problems with an interior-point method, Unnamed Item, An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem, Exploring the Subexponential Complexity of Completion Problems, Approximation algorithms in combinatorial scientific computing, Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work, Unnamed Item, Unnamed Item, Decision Diagram Decomposition for Quadratically Constrained Binary Optimization, Decomposable Probabilistic Influence Diagrams, The Complexity of the Partial Order Dimension Problem, Bayesian networks: the minimal triangulations of a graph, Unnamed Item, Vertex Deletion Problems on Chordal Graphs, Customizable Contraction Hierarchies, PMORSy: parallel sparse matrix ordering software for fill-in minimization
Cites Work
