Packing edge disjoint triangles: A parameterized view

L. Mathieson, E Prieto, P. Shaw

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

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. © Springer-Verlag 2004.
Original languageEnglish
Title of host publicationParameterized and Exact Computation
Subtitle of host publicationFirst International Workshop, IWPEC 2004, Bergen, Norway, September 14-17, 2004. Proceedings
EditorsRod Downey, Michael Fellows, Frank Dehne
PublisherSpringer
Pages127-137
Number of pages11
ISBN (Electronic)978-3-540-28639-4
ISBN (Print)978-3-540-23071-7
DOIs
Publication statusPublished - 2004
Externally publishedYes

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3162
ISSN (Print)0302-9743

Cite this