Maximum induced matchings for chordal graphs in linear time
type: Item
instance of: scholarly article
title: Maximum induced matchings for chordal graphs in linear time
zbMATH Open document ID: 1171.68595
author: Andreas Brandstädt
author: Chính T. Hoàng
published in: Algorithmica
publication date: 2009-05-13T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5553557
zbMATH Keywords: maximum induced matchings
zbMATH Keywords: chordal graphs
zbMATH Keywords: perfect elimination order
zbMATH Keywords: lexicographic breadth-first search
zbMATH Keywords: linear time algorithm
MaRDI profile type: Publication
full work available at URL: s00453-007-9045-2
OpenAlex ID: W1999576733
cites work: LexBFS-orderings and powers of chordal graphs
cites work: Induced matchings
cites work: Induced matchings in intersection graphs
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Induced matchings in asteroidal triple-free graphs
cites work: Q3139292
cites work: Q3328583
cites work: Irredundancy in circular arc graphs
cites work: New results on induced matchings
cites work: Bipartite Domination and Simultaneous Matroid Covers
cites work: Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: Q4500845
DOI: 10.1007/S00453-007-9045-2
Recommended article: Finding a maximum induced matching in weakly chordal graphs
Recommended article: Maximum induced matchings in graphs
Recommended article: Maximum vertex-weighted matching in strongly chordal graphs
Recommended article: Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
Recommended article: On maximum induced matchings in bipartite graphs
Recommended article: Approximation and Online Algorithms
Recommended article: Induced matchings in graphs of bounded maximum degree
Recommended article: Maximum induced matching algorithms via vertex ordering characterizations
Recommended article: Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
Recommended article: A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
description: scientific article; zbMATH DE number 5553557