Paired domination on interval and circular-arc graphs

Research output: Journal article publicationJournal articleAcademic researchpeer-review

42 Citations (Scopus)

Abstract

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O (m + n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O (m (m + n)) time.
Original languageEnglish
Pages (from-to)2077-2086
Number of pages10
JournalDiscrete Applied Mathematics
Volume155
Issue number16
DOIs
Publication statusPublished - 1 Oct 2007

Keywords

  • Circular-arc graph
  • Interval graph
  • Paired domination

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Applied Mathematics
  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Cite this