On the domatic number of interval graphs

DOI10.1016/0020-0190(88)90173-1MaRDI QIDQ1111388zbMATH OpenOpenAlexFDO

Authors Alan A. Bertossi

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90173-1

zbMATH Keywords

dominating setinterval graphsdomatic number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The Domatic Number Problem in Interval Graphs
• Finding a Domatic Partition of an Interval Graph in Time $O(n)$
• Linear algorithm for domatic number problem on interval graphs
• Total domination in interval graphs
• Dominating sets and domatic number of circular arc graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An 0(n log n) algorithm for the convex bipartite matching problem
• Dominating Sets in Chordal Graphs
• Dominating sets and domatic number of circular arc graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Some parallel algorithms on interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Total Domination and Irredundance in Weighted Interval Graphs
• Total domination in interval graphs

Cited in

(23)

• scientific article; zbMATH DE number 1011262 (Why is no real title available?)
• A tight bound on the number of mobile servers to guarantee transferability among dominating configurations
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• On counting interval lengths of interval graphs
• Connected domination and Steiner set on weighted permutation graphs
• Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction
• The domatic number problem
• Finding domatic partitions in infinite graphs
• On dominating set polyhedra of circular interval graphs
• Dominating sets and domatic number of circular arc graphs
• On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
• On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products
• scientific article; zbMATH DE number 894698 (Why is no real title available?)
• Loose cover of graphs
• The Domatic Number Problem in Interval Graphs
• Edge domatic numbers of complete \(n\)-partite graphs
• The k-neighbor, r-domination problems on interval graphs
• A resource assignment problem on graphs
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• Linear algorithm for domatic number problem on interval graphs
• The Total Interval Number of a Graph II: Trees and Complexity
• An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model
• Weighted independent perfect domination on cocomparability graphs

This page was built for publication: On the domatic number of interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111388)