Weighted independent perfect domination on cocomparability graphs
type: Item
instance of: scholarly article
title: Weighted independent perfect domination on cocomparability graphs
zbMATH Open document ID: 0848.05039
DOI: 10.1016/0166-218X(94)00067-3
author: C. Pandu Rangan
author: Satyan Coorg
author: Gerard Jennhwa Chang
published in: Discrete Applied Mathematics
publication date: 1996-08-05T00:00:00Z
review text: Let \(G = (V,E)\) be a graph in which every vertex \(v \in V\) is associated with a cost \(c(v)\). A graph is cocomparability graph if its vertex set has a cocomparability ordering, which is a labelling of \(V\) with \(1,2, \dots, n\) such that \[ i < j < k \quad \text{and} \quad (i,k) \in E \quad \text{imply} \quad (i,j) \in E \quad \text{or} \quad (j,k) \in E. \] In this paper, the authors study the problem of finding a subset \(D\) of \(V\) such that every vertex in \(V\) is equal or adjacent to exactly one vertex in \(D\) and \(\sum_{v \in D} c(v)\) is minimized. They give an \(O(|V |\cdot |E |)\) algorithm for the problem on cocomparability graphs. The algorithm can be modified slightly to run in \(O(|V |^{2.37})\) time. With some modifications, the algorithm can be adapted to take \(O(|V |+ |E |)\) time on interval graphs, which are special cocomparability graphs.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 897345
zbMATH Keywords: perfect domination
zbMATH Keywords: cocomparability graph
zbMATH Keywords: cocomparability ordering
zbMATH Keywords: labelling
MaRDI profile type: Publication
cites work: Efficient parallel algorithms for permutation graphs
cites work: Q3815323
cites work: Total domination in interval graphs
cites work: On the domatic number of interval graphs
cites work: Total Domination and Irredundance in Weighted Interval Graphs
cites work: Perfect codes in graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
cites work: Q3328583
cites work: An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
cites work: Domination on Cocomparability Graphs
cites work: Q5284096
cites work: The Domatic Number Problem in Interval Graphs
cites work: Total domination in interval graphs revisited
cites work: A unified approach to domination problems on interval graphs
cites work: Q4035766
cites work: Linear algorithm for domatic number problem on interval graphs
cites work: The weighted perfect domination problem
cites work: A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
cites work: The weighted perfect domination problem and its variants
description: scientific article; zbMATH DE number 897345