Minimum dominating sets of intervals on lines

DOI10.1007/BFB0030873MaRDI QIDQ6064049zbMATH OpenOpenAlexFDO

Authors Siu-Wing Cheng, Michael Kaminski, Shmuel Zaks

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030873

zbMATH Keywords

interval graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Minimum dominating sets of intervals on lines
• Minimum connected dominating sets of intervals on lines
• On minimum intersection of two minimum dominating sets of interval graphs
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Total domination in interval graphs

Cites work

• A linear-time algorithm for a special case of disjoint set union
• A unified approach to domination problems on interval graphs
• Dominating Sets in Chordal Graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 4041287 (Why is no real title available?)
• Priority Search Trees
• Total Domination and Irredundance in Weighted Interval Graphs

Cited in

(2)

• Geometric dominating sets -- a minimum version of the no-three-in-line problem
• Efficient maintenance of the union of intervals on a line, with applications

This page was built for publication: Minimum dominating sets of intervals on lines

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