Leaf sector covers with applications on circle graphs

DOI10.1016/J.TCS.2024.114619MaRDI QIDQ6549679zbMATH OpenFDO

Authors Ta-Yu Mu, Po-Yuan Wang, Ching-Chi Lin

Publication date 4 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114619

zbMATH Keywords

approximation algorithmcircle graphpaired-dominationtotal domination

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 algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1445364
• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• scientific article; zbMATH DE number 1522922
• Dominating sets and domatic number of circular arc graphs
• The complexity of domination problems in circle graphs

Cites work

• A (2+ε)-Approximation Scheme for Minimum Domination on Circle Graphs
• A decomposition approach for solving a broadcast domination network design problem
• A dominating-set-based routing scheme in ad hoc wireless networks
• A linear-time algorithm for paired-domination on circular-arc graphs
• A linear-time algorithm for paired-domination problem in strongly chordal graphs
• A polynomial-time algorithm for the paired-domination problem on permutation graphs
• A survey of selected recent results on total domination in graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• An \(O(n)\)-time algorithm for the paired domination problem on permutation graphs
• Bibliography on domination in graphs and some basic definitions of domination parameters
• Domination criticality in product graphs
• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• scientific article; zbMATH DE number 1302196 (Why is no real title available?)
• scientific article; zbMATH DE number 1354123 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Improved algorithms and complexity results for power domination in graphs
• Independent domination in graphs: A survey and recent results
• Infectious power domination of hypergraphs
• Labelling algorithms for paired-domination problems in block and interval graphs
• Minimum Fill-in on Circle and Circular-Arc Graphs
• Paired-domination in graphs
• Paired-domination of trees
• Practical and efficient circle graph recognition
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• The complexity of domination problems in circle graphs
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Topics on domination
• Total domination and transformation

This page was built for publication: Leaf sector covers with applications on circle graphs

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