Maximum vertex-weighted matching in strongly chordal graphs

DOI10.1016/S0166-218X(97)00136-4MaRDI QIDQ1392564zbMATH OpenFDO

Authors Manoel Campêlo, Sulamita Klein

Publication date 28 July 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

linear time algorithmmatchingstrongly chordal graphvertex-weight

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• Matching and multidimensional matching in chordal and strongly chordal graphs
• scientific article; zbMATH DE number 3902700
• scientific article; zbMATH DE number 4198027
• Strongly maximal matchings in infinite graphs
• A recurrent algorithm to solve the weighted matching problem

Cites work

• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Doubly Lexical Orderings of Matrices
• Matching is as easy as matrix inversion
• Three Partition Refinement Algorithms

Cited in

(6)

• Strongly maximal matchings in infinite graphs
• Maximum induced matchings for chordal graphs in linear time
• On the total weight of weighted matchings of segment graphs
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs
• scientific article; zbMATH DE number 4198027 (Why is no real title available?)

This page was built for publication: Maximum vertex-weighted matching in strongly chordal graphs

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