Efficient algorithms for the minimum connected domination on trapezoid graphs

DOI10.1016/j.ins.2007.02.001zbMath1116.68064OpenAlexW2058781294MaRDI QIDQ881872

Yin Te Tsai, Yaw-Ling Lin, Fang-Rong Hsu

Publication date: 18 May 2007

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2007.02.001

zbMATH Keywords

dominating settrapezoid graphsalgorithms and data structures(weighted) connected dominating set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (8)

Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ Independent rainbow domination of graphs ⋮ On the \(k\)-tuple domination of generalized de Brujin and Kautz digraphs ⋮ On rainbow domination numbers of graphs ⋮ Finding minimum weight connected dominating set in stochastic graph based on learning automata ⋮ Counting the number of vertex covers in a trapezoid graph ⋮ The hub number of co-comparability graphs ⋮ Linear separation of connected dominating sets in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and their coloring
• Preserving order in a forest in less than logarithmic time and linear space
• Dominations in trapezoid graphs
• Weighted domination of cocomparability graphs
• Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs
• Connected domination and dominating clique in trapezoid graphs
• Domination on Cocomparability Graphs
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• Graph Classes: A Survey
• On the 2-Chain Subgraph Cover and Related Problems

This page was built for publication: Efficient algorithms for the minimum connected domination on trapezoid graphs