Maximal chordal subgraphs

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

zbMATH Keywords

algorithmchordal graphsmaximum independent setmaximal chordal subgraphsolving sparse systems of linear equations

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

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