Dominating sets and domatic number of circular arc graphs
type: Item
instance of: scholarly article
title: Dominating sets and domatic number of circular arc graphs
zbMATH Open document ID: 0579.05051
DOI: 10.1016/0166-218X(85)90025-3
author: Maurizio A. Bonuccelli
published in: Discrete Applied Mathematics
publication date: 1985-01-01T00:00:00Z
review text: This paper presents an O(n\(| E|)\) time algorithm for finding a minimum cardinality dominating set of a circular arc graph. The domatic number problem (finding a maximum cardinality partition of the nodes into dominating sets) is solved in \(O(n^ 2 \log n)\) time for a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3926969
zbMATH Keywords: circular arc graph
zbMATH Keywords: domatic number
zbMATH Keywords: dominating sets
MaRDI profile type: Publication
cites work: On domination and independent domination numbers of a graph
cites work: On a routing problem
cites work: Construction of TernaryHv-groups and TernaryP-hyperoperations
cites work: Q3941433
cites work: Minimum node disjoint path covering for circular-arc graphs
cites work: Dominating Sets in Chordal Graphs
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: Total domination in graphs
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: A linear algorithm for the domination number of a tree
cites work: Towards a theory of domination in graphs
cites work: Disjoint independent dominating sets in graphs
cites work: Domination, independent domination, and duality in strongly chordal graphs
cites work: Domination in permutation graphs
cites work: Q4198056
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Algorithms on circular-arc graphs
cites work: Q3328583
cites work: An Optimal Solution for the Channel-Assignment Problem
cites work: A linear algorithm for the domination number of a series-parallel graph
cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
cites work: Q4138414
cites work: R -Domination in Graphs
cites work: Coloring a Family of Circular Arcs
cites work: An Efficient Test for Circular-Arc Graphs
full work available at URL: 0166-218x(85)90025-3
OpenAlex ID: W2143180579
description: scientific article; zbMATH DE number 3926969