Connected domination and steiner set on asteroidal triple-free graphs

DOI10.1007/3-540-57155-8_242MaRDI QIDQ5060107zbMATH OpenOpenAlexFDO

Authors Hari Balakrishnan, A. Rajaraman, C. Pandu Rangan

Publication date 18 January 2023

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

Full work available at URL https://doi.org/10.1007/3-540-57155-8_242

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Domination and total domination on asteroidal triple-free graphs
• A linear time algorithm to compute a dominating path in an AT-free graph
• Asteroidal Triple-Free Graphs
• Independent Sets in Asteroidal Triple-Free Graphs
• Independent sets in asteroidal triple-free graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Connected domination and Steiner set on weighted permutation graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Dominating sets in perfect graphs
• Representation of a finite graph by a set of intervals on the real line
• Steiner trees, connected domination and strongly chordal graphs

Cited in

(9)

• A note on the geodetic number and the Steiner number of AT-free graphs
• Parameterized complexity of multicut in weighted trees
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Connected feedback vertex set on AT-free graphs
• Domination and total domination on asteroidal triple-free graphs
• Connected feedback vertex set on AT-free graphs
• Domination and Cut Problems on Chordal Graphs with Bounded Leafage
• Computing a dominating pair in an asteroidal triple-free graph in linear time
• A linear time algorithm to compute a dominating path in an AT-free graph

This page was built for publication: Connected domination and steiner set on asteroidal triple-free graphs

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