Computing the Minimum Fill-In is NP-Complete
From MaRDI portal
Cites work
- Algorithmic Aspects of Vertex Elimination on Directed Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Node-Deletion Problems on Bipartite Graphs
- Some simplified NP-complete graph problems
Cited in
(only showing first 100 items - show all)- Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
- Coreduction homology algorithm
- The graph sandwich problem for P₄-sparse graphs
- Exploiting special structure in semidefinite programming: a survey of theory and applications
- Decomposition by clique separators
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Efficient solutions of hierarchical systems of linear equations
- Bipartite permutation graphs
- The analysis of a nested dissection algorithm
- Maximal chordal subgraphs
- Solution of sparse positive definite systems on a hypercube
- An appraisal of computational complexity for operations researchers
- The average parallel complexity of Cholesky factorization
- The complexity of reconstructing trees from qualitative characters and subtrees
- Triangulating graphs with few \(P_4\)'s
- Decomposing constraint satisfaction problems using database techniques
- An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
- Finding minimum height elimination trees for interval graphs in polynomial time
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Triangulating multitolerance graphs
- A practical algorithm for making filled graphs minimal
- Listing all potential maximal cliques of a graph
- An implementation of the iterative proportional fitting procedure by propagation trees.
- Decomposition in multidimensional Boolean-optimization problems with sparse matrices
- The isomorphic version of Brualdi's and Sanderson's nestedness
- An introduction to clique minimal separator decomposition
- On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
- Distance descending ordering method: an \(O(n)\) algorithm for inverting the mass matrix in simulation of macromolecules with long branches
- An \(O(n^2)\) time algorithm for the minimal permutation completion problem
- Minimal separators in extended \(P_4\)-laden graphs
- Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts
- Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
- Graphical models for genetic analyses
- Vertex deletion problems on chordal graphs
- On sum coloring of graphs
- An implementation of Karmarkar's algorithm for linear programming
- Linear time optimization algorithms for \(P_ 4\)-sparse graphs
- Optimal labelling of unit interval graphs
- A local reductive elimination for the fill-in of graphs
- Triangulating graphs without asteroidal triples
- Proper interval vertex deletion
- Domination and total domination on asteroidal triple-free graphs
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- Efficiently enumerating minimal triangulations
- On tradeoffs between width- and fill-like graph parameters
- A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods
- Solution methods for the vertex variant of the network system vulnerability analysis problem
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Learning chordal extensions
- A triangulation and fill-reducing initialization procedure for the simplex algorithm
- QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programs
- Efficient function approximation on general bounded domains using splines on a Cartesian grid
- On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
- Bipartite completion of colored graphs avoiding chordless cycles of given lengths
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Exploiting sparsity for the min \(k\)-partition problem
- Parikh word representability of bipartite permutation graphs
- Hypergraph edge elimination -- a symbolic phase for Hermitian eigensolvers based on rank-1 modifications
- COSMO: a conic operator splitting method for convex conic problems
- On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs
- Edge deletion problems: branching facilitated by modular decomposition
- Minimum fill-in of sparse graphs: kernelization and approximation
- Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
- Some completion problems for graphs without chordless cycles of prescribed lengths
- Large-scale problems with quasi-block matrices
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
- Minimum fill-in: inapproximability and almost tight lower bounds
- Bayesian networks: the minimal triangulations of a graph
- Updating credal networks is approximable in polynomial time
- All roads lead to Rome -- new search methods for the optimal triangulation problem
- Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
- A polynomial-time algorithm for outerplanar diameter improvement
- Automating algorithm selection: checking for matrix properties that can simplify computations
- A cubic-vertex kernel for flip consensus tree
- Digraphs of bounded elimination width
- Searching for better fill-in
- NP-hard graph problems and boundary classes of graphs
- Minimal comparability completions of arbitrary graphs
- Tree decomposition and discrete optimization problems: a survey
- On the interval completion of chordal graphs
- NP-completeness results for edge modification problems
- Complexity of modification problems for best match graphs
- Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
- Parallelized integrated nested Laplace approximations for fast Bayesian inference
- A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
- Cooperative triangulation in MSBNs without revealing subnet structures
- Robustness to dependency in portfolio optimization using overlapping marginals
- Parameterized enumeration for modification problems
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Exploring the subexponential complexity of completion problems
- Planar disjoint-paths completion
- The homogeneous set sandwich problem
- Chordal editing is fixed-parameter tractable
- Recognizing sparse perfect elimination bipartite graphs
- scientific article; zbMATH DE number 5818908 (Why is no real title available?)
- Approximation algorithms for minimum chain vertex deletion
- Polynomial kernels for proper interval completion and related problems
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)
