On the domatic number of interval graphs

DOI10.1016/0020-0190(88)90173-1zbMATH Open0658.68077OpenAlexW1991307540MaRDI QIDQ1111388FDOQ1111388

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

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

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)

Cites Work

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

Cited In (23)

• Title not available (Why is that?)
• 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
• Maximum Connected Domatic Partition of Directed Path Graphs with Single Junction
• Connected domination and Steiner set on weighted permutation graphs
• 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 \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products
• On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset
• Title not available (Why is that?)
• Loose cover of graphs
• The Domatic Number Problem in Interval Graphs
• A resource assignment problem on graphs
• Edge domatic numbers of complete \(n\)-partite graphs
• The \(k\)-neighbor, \(r\)-domination problems on interval graphs
• The Total Interval Number of a Graph II: Trees and Complexity
• A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
• Linear algorithm for domatic number problem on interval graphs
• Weighted independent perfect domination on cocomparability graphs
• An optimal parallel algorithm for the domatic partition problem on an interval graph given its sorted model

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)