Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs

The Induced Graph Matching problem asks to find$$k$$ k disjoint induced subgraphs isomorphic to a given graph $$H$$ H in a given graph$$G$$ G such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and Induced Matching problems, am...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 70, No. 3 (2014), p. 513-560
Main Author: Hermelin, Danny
Other Involved Persons: Mnich, Matthias ; Leeuwen, Jan
Format: electronic Article
Language:English
ISSN:1432-0541
Item Description:An extended abstract of the results in this paper have appeared in the Proceedings of 20th European Symposium on Algorithms (ESA 2012) [26]. Partially supported by ERC StG project PAAl No. 259515. The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007–2013) under REA grant agreement No. 631163.11.
Physical Description:Online-Ressource
DOI:10.1007/s00453-014-9877-5
Subjects:
QR Code: Show QR Code