A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
type: Item
instance of: scholarly article
title: A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
author: Peng Li
author: Aifa Wang
author: Jianhui Shang
published in: Journal of Combinatorial Optimization
publication date: 2022-12-12T00:00:00Z
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 7632070
zbMATH Keywords: domination
zbMATH Keywords: \(k\)-tuple domination
zbMATH Keywords: total \(k\)-domination
zbMATH Keywords: \(k\)-domination
zbMATH Keywords: linear time algorithm
zbMATH Keywords: interval graph
MaRDI profile type: Publication
full work available at URL: s10878-022-00932-4
OpenAlex ID: W4309699545
cites work: Complexity of \(k\)-tuple total and total \(\{k\}\)-dominations for some subclasses of bipartite graphs
cites work: Minimum 2-tuple dominating set of permutation graphs
cites work: Graph classes with structured neighborhoods and algorithmic applications
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
cites work: Trees with equal 2-domination and 2-independence numbers
cites work: \(k\)-domination and \(k\)-independence in graphs: A survey
cites work: New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
cites work: On the approximability and exact algorithms for vector domination and related problems in graphs
cites work: The LBFS Structure and Recognition of Interval Graphs
cites work: Onk-domination and minimum degree in graphs
cites work: Q3691778
cites work: Q3344239
cites work: Algorithmic graph theory and perfect graphs
cites work: On \(k\)-domination and \(j\)-independence in graphs
cites work: Q4552196
cites work: Q4368729
cites work: Q4368728
cites work: \(k\)-tuple total domination in graphs
cites work: Q4734763
cites work: A width parameter useful for chordal and co-comparability graphs
cites work: On the total k-domination number of graphs
cites work: Q3976627
cites work: Algorithmic aspects of the \(k\)-domination problem in graphs
cites work: On the algorithmic complexity of \(k\)-tuple total domination
cites work: Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
cites work: A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
cites work: Optimal greedy algorithms for indifference graphs
cites work: Q3686754
cites work: Algorithmic aspects of \(k\)-tuple total domination in graphs
cites work: Minimum 2-tuple dominating set of an interval graph
cites work: A unified approach to domination problems on interval graphs
cites work: Q3783331
cites work: The longest cycle problem is polynomial on interval graphs
cites work: Q4352951
DOI: 10.1007/S10878-022-00932-4
description: scientific article; zbMATH DE number 7632070