Packing edge disjoint triangles

A parameterized view

Luke Mathieson, Elena Prieto, Peter Shaw

Research output: Contribution to journalArticle

29 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)127-137
Number of pages11
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3162
Publication statusPublished - 2004

Fingerprint Dive into the research topics of 'Packing edge disjoint triangles: A parameterized view'. Together they form a unique fingerprint.

  • Cite this