Maximal chordal subgraphs
From MaRDI portal
Publication:1115455
DOI10.1016/0166-218X(88)90075-3zbMath0664.05032OpenAlexW2072679355MaRDI QIDQ1115455
P. M. Dearing, Daniel D. Warner, Douglas R. Shier
Publication date: 1988
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(88)90075-3
algorithmchordal graphsmaximum independent setmaximal chordal subgraphsolving sparse systems of linear equations
Related Items
Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Chordal editing is fixed-parameter tractable, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Iterative proportional scaling via decomposable submodels for contingency tables, On the complexity of some subgraph problems, Maximal sub-triangulation in pre-processing phylogenetic data, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, On the structure of linear programs with overlapping cardinality constraints, A chordal preconditioner for large-scale optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- Some aspects of perfect elimination orderings in chordal graphs
- A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
- Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Finding a Maximum Clique in an Arbitrary Graph
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Edge-Deletion Problems
- Computing the Minimum Fill-In is NP-Complete
- Vertex packings: Structural properties and algorithms
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Survey of Lagrangean Techniques for Discrete Optimization