Dabrowski, Konrad, Demange, Marc and Lozin, Vadim V. (2013) New results on maximum induced matchings in bipartite graphs and beyond. Theoretical Computer Science, Volume 478 . pp. 33-40. doi:10.1016/j.tcs.2013.01.027 ISSN 0304-3975.

Research output not available from this repository.

Request-a-Copy directly from author or use local Library Get it For Me service.

Request Changes to record.

Abstract

The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i.e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution.

Item Type:	Journal Article
Divisions:	Faculty of Science, Engineering and Medicine > Science > Mathematics
Journal or Publication Title:	Theoretical Computer Science
Publisher:	Elsevier Science BV
ISSN:	0304-3975
Official Date:	25 March 2013
Dates:	Date Event 25 March 2013 Published
Volume:	Volume 478
Page Range:	pp. 33-40
DOI:	10.1016/j.tcs.2013.01.027
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Funder:	Centre for Discrete Mathematics and its Applications (DIMAP), Engineering and Physical Sciences Research Council (EPSRC), French Agency for Research under the DEFIS program TODO
Grant number:	EP/D063191/1, EP/101795X/1 (EPSRC); ANR-09-EMER-010 (TODO)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item