The matching extension problem in general graphs is co-NP-complete
type: Item
instance of: scholarly article
title: The matching extension problem in general graphs is co-NP-complete
zbMATH Open document ID: 1387.05203
author: Jan Hackfeld
author: Arie M. C. A. Koster
published in: Journal of Combinatorial Optimization
publication date: 2018-04-13T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6859592
zbMATH Keywords: complexity
zbMATH Keywords: perfect matching
zbMATH Keywords: extendability
MaRDI profile type: Publication
full work available at URL: s10878-017-0226-x
OpenAlex ID: W2775963553
cites work: Paths, Trees, and Flowers
cites work: Reducibility among Combinatorial Problems
cites work: A polynomial algorithm for the extendability problem in bipartite graphs
cites work: Extending matchings in graphs: A survey
cites work: Recent Progress in Matching Extension
cites work: Construction for bicritical graphs and \(k\)-extendable bipartite graphs
DOI: 10.1007/S10878-017-0226-X
Recommended article: Generalization of matching extensions in graphs
Recommended article: Extending matchings in graphs: A survey
Recommended article: Q4393233
Recommended article: Generalization of matching extensions in graphs. II.
Recommended article: Q4528770
Recommended article: On the complexity of some problems related to graph extensions
Recommended article: Generalization of matching extensions in graphs. III
Recommended article: Matchings and matching extensions in graphs
Recommended article: Q4873744
Recommended article: Q5202207
description: scientific article; zbMATH DE number 6859592