Maximal chordal subgraphs
type: Item
instance of: scholarly article
title: Maximal chordal subgraphs
zbMATH Open document ID: 0664.05032
DOI: 10.1016/0166-218X(88)90075-3
author: P. M. Dearing
author: Douglas R. Shier
author: Daniel D. Warner
published in: Discrete Applied Mathematics
publication date: 1988-01-01T00:00:00Z
review text: A graph G is chordal if it does not contain any cycle of length greater than 3 as an induced subgraph. The authors thoroughly motivate the study of chordal graphs. An algorithm for finding a maximal chordal subgraph of an arbitrary graph G is presented. It is shown that this algorithm can be implemented with a worst-case time complexity bound of 0(\(| E| \Delta)\) where \(\Delta\) is the maximum degree among the vertices of G. It is then shown that the maximum independent set problem can be formulated using maximal chordal subgraphs. It is pointed out that this formulation is stronger than the customary edge-vertex formulation and leads to a Lagrangian relaxation approach. The authors then show how maximal chordal subgraphs can be used to define a splitting for the coefficient matrix of a large sparse system of linear equations. This splitting is then used to produce iterative schemes for solving the original system of equations.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 4085687
zbMATH Keywords: solving sparse systems of linear equations
zbMATH Keywords: chordal graphs
zbMATH Keywords: algorithm
zbMATH Keywords: maximal chordal subgraph
zbMATH Keywords: maximum independent set
reviewed by: Ortrud R. Oellermann
MaRDI profile type: Publication
cites work: A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
cites work: Finding a Maximum Clique in an Arbitrary Graph
cites work: Q3943082
cites work: Q4079014
cites work: Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method
cites work: On rigid circuit graphs
cites work: The Lagrangian Relaxation Method for Solving Integer Programming Problems
cites work: Q4093489
cites work: Incidence matrices and interval graphs
cites work: Q3328583
cites work: Q4192890
cites work: Vertex packings: Structural properties and algorithms
cites work: Triangulated graphs and the elimination process
cites work: Q5683627
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: A Survey of Lagrangean Techniques for Discrete Optimization
cites work: Some aspects of perfect elimination orderings in chordal graphs
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
cites work: Q5342712
cites work: Edge-Deletion Problems
cites work: Computing the Minimum Fill-In is NP-Complete
full work available at URL: 0166-218x(88)90075-3
OpenAlex ID: W2072679355
description: scientific article; zbMATH DE number 4085687