Computing the Minimum Fill-In is NP-Complete
From MaRDI portal
Publication:3960122
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3420184 (Why is no real title available?)
- Algorithmic Aspects of Vertex Elimination on Directed Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Node-Deletion Problems on Bipartite Graphs
- Some simplified NP-complete graph problems
Cited in
(only showing first 100 items - show all)- Pathwidth is NP-Hard for Weighted Trees
- An \(\mathcal O(n^2)\)-time algorithm for the minimal interval completion problem
- Polynomial kernels for proper interval completion and related problems
- Graphical Models and Message-Passing Algorithms: Some Introductory Lectures
- A Subexponential Parameterized Algorithm for Proper Interval Completion
- A linear time algorithm to list the minimal separators of chordal graphs
- Lex M versus MCS-M
- Solving quadratically constrained convex optimization problems with an interior-point method
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Efficient solutions of hierarchical systems of linear equations
- Minimal elimination ordering for graphs of bounded degree
- On sparse matrix orderings in interior point methods
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- How to use the minimal separators of a graph for its chordal triangulation
- scientific article; zbMATH DE number 7765420 (Why is no real title available?)
- Characterizing and computing minimal cograph completions
- Decomposition methods for sparse matrix nearness problems
- Graphical models for genetic analyses
- Treewidth and minimum fill-in on permutation graphs in linear time
- A survey of direct methods for sparse linear systems
- Hypergraph edge elimination -- a symbolic phase for Hermitian eigensolvers based on rank-1 modifications
- On computing large temporal (unilateral) connected components
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Bayesian networks: the minimal triangulations of a graph
- Parameterized enumeration for modification problems
- A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs
- scientific article; zbMATH DE number 2230201 (Why is no real title available?)
- Tree decomposition and discrete optimization problems: a survey
- Customizable contraction hierarchies
- 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
- On 3-degree 4-chordal graphs
- Graph classes and the switch Markov chain for matchings
- Minimal split completions
- On the ordering of sparse linear systems
- Hardness results and an exact exponential algorithm for the spanning tree congestion problem
- NP-completeness results for edge modification problems
- On tradeoffs between width- and fill-like graph parameters
- Global minimization of polynomial integral functionals
- The graph sandwich problem for P₄-sparse graphs
- Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
- The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration
- On listing, sampling, and counting the chordal graphs with edge constraints
- A Separator Theorem for Chordal Graphs
- Linear optimization over homogeneous matrix cones
- Parallelized integrated nested Laplace approximations for fast Bayesian inference
- Algorithms and complexity of sandwich problems in graphs (extended abstract)
- A vertex incremental approach for maintaining chordality
- Edge deletion problems: branching facilitated by modular decomposition
- Characterizations and algorithmic applications of chordal graph embeddings
- On treewidth and minimum fill-in of asteroidal triple-free graphs
- Discovering a junction tree behind a Markov network by a greedy algorithm
- Searching for better fill-in
- Exploiting special structure in semidefinite programming: a survey of theory and applications
- Proper interval vertex deletion
- Decomposition by clique separators
- An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
- Fixed-parameter tractability of graph modification problems for hereditary properties
- The complexity of reconstructing trees from qualitative characters and subtrees
- Transmission operators for the non-overlapping Schwarz method for solving Helmholtz problems in rectangular cavities
- Algebras for tree decomposable graphs
- Approximating the Minimum Chain Completion problem
- 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
- Exact solution of sparse linear systems via left-looking roundoff-error-free Lu factorization in time proportional to arithmetic work
- Minimal triangulations of graphs: a survey
- Triangulating graphs without asteroidal triples
- A cubic-vertex kernel for flip consensus tree
- 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
- Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
- Approximation algorithms in combinatorial scientific computing
- An introduction to clique minimal separator decomposition
- Parikh word representability of bipartite permutation graphs
- Bipartite permutation graphs
- Vertex deletion problems on chordal graphs
- Fast minimal triangulation algorithm using minimum degree criterion
- On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
- scientific article; zbMATH DE number 7053390 (Why is no real title available?)
- The General Minimum Fill-In Problem
- Minimal separators in extended \(P_4\)-laden graphs
- Characterizing and Computing Minimal Cograph Completions
- On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
- Computing Tree Decompositions
- Decomposition in multidimensional Boolean-optimization problems with sparse matrices
- A local reductive elimination for the fill-in of graphs
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Bipartite completion of colored graphs avoiding chordless cycles of given lengths
- Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
- Complexity classification of some edge modification problems
- Robustness to dependency in portfolio optimization using overlapping marginals
- A survey of parameterized algorithms and the complexity of edge modification
- Chordal deletion is fixed-parameter tractable
- Computational aspects of DNA mixture analysis
- On the interval completion of chordal graphs
- On computing large temporal (unilateral) connected components
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)
