Maximal chordal subgraphs

DOI10.1016/0166-218X(88)90075-3zbMATH Open0664.05032OpenAlexW2072679355MaRDI QIDQ1115455FDOQ1115455

Authors: P. M. Dearing, Douglas R. Shier, Daniel D. Warner 

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

Recommendations

• The maximum k-colorable subgraph problem for chordal graphs
• Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution
• On the complexity of some subgraph problems
• A Separator Theorem for Chordal Graphs
• scientific article; zbMATH DE number 554762

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Incidence matrices and interval graphs
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• On rigid circuit graphs
• Vertex packings: Structural properties and algorithms
• Title not available (Why is that?)
• 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
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computing the Minimum Fill-In is NP-Complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Edge-Deletion Problems
• A Survey of Lagrangean Techniques for Discrete Optimization
• Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method
• Some aspects of perfect elimination orderings in chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring

Cited In (18)

• Iterative proportional scaling via decomposable submodels for contingency tables
• Maximal chains of isomorphic subgraphs of the Rado graph
• A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
• On the complexity of some subgraph problems
• Title not available (Why is that?)
• A vertex incremental approach for maintaining chordality
• Chordal editing is fixed-parameter tractable
• Minimal triangulations of graphs: a survey
• Title not available (Why is that?)
• Maximal sub-triangulation in pre-processing phylogenetic data
• A chordal preconditioner for large-scale optimization
• On the minimum chordal completion polytope
• Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications
• Edge erasures and chordal graphs
• On the structure of linear programs with overlapping cardinality constraints
• Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
• Finding a maximum-weight convex set in a chordal graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

This page was built for publication: Maximal chordal subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115455)