Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Packing Edge Disjoint Triangles: A Parameterized View

Mathieson, Luke, Prieto, Elena and Shaw, Peter (2004). Packing Edge Disjoint Triangles: A Parameterized View<br />. Lecture Notes in Computer Science,3162:127-137.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

Title Packing Edge Disjoint Triangles: A Parameterized View
Author Mathieson, Luke
Prieto, Elena
Shaw, Peter
Journal Name Lecture Notes in Computer Science
Publication Date 2004
Volume Number 3162
ISSN 0302-9743   (check CDU catalogue  open catalogue search in new window)
Start Page 127
End Page 137
Total Pages 11
Place of Publication Germany
Publisher Springer
HERDC Category C1 - Journal Article (DIISR)
Abstract The problem of packing k edge-disjoint triangles in a graph has been thoroughly studied both in the classical complexity and the approximation fields and it has a wide range of applications in many areas, especially computational biology [BP96]. In this paper we present an analysis of the problem from a parameterized complexity viewpoint. We describe a fixed-parameter tractable algorithm for the problem by means of kernelization and crown rule reductions, two of the newest techniques for fixed-parameter algorithm design. We achieve a kernel size bounded by 4k, where k is the number of triangles in the packing.
DOI http://dx.doi.org/10.1007/978-3-540-28639-4_12   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
Additional Notes Monographic series - Booktitle: Parameterized and Exact Computation - Volume 3162 of the Series: Lecture Notes in Computer Science pp 127-137. Print ISBN: 978-3-540-23071-7; Online ISBN:978-3-540-28639-4
Description for Link Link to publisher's version
URL http://link.springer.com/chapter/10.1007%2F978-3-540-28639-4_12
 
Versions
Version Filter Type
Access Statistics: 7 Abstract Views  -  Detailed Statistics
Created: Tue, 03 Nov 2015, 12:19:50 CST by Marion Farram