Domination and total domination on asteroidal triple-free graphs
An asteroidal triple (AT) of an undirected graph \(G\) is a set of three vertices of \(G\) such that there is a path between any two of them avoiding the neighborhood of the third one. A graph is AT-free if it contains no AT. The structure and algorithmic properties of AT-free graphs have been studied extensively---AT-free graphs generalize well-known graph classes such as interval, permutation, trapezoid and cocomparability graphs. This paper presents polynomial time algorithms for solving the problems DOMINATING SET and TOTAL DOMINATING SET restricted to AT-free graphs. These algorithms even work in polynomial time on graphs with dominating shortest path---a generalization of AT-free graphs. The key idea of the algorithms is to compute a certain type of dominating set by dynamic programming through the levels of a BFS-tree.
- Computing a dominating pair in an asteroidal triple-free graph in linear time
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Independent sets in asteroidal triple-free graphs
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- Connected domination and steiner set on asteroidal triple-free graphs
- A linear time algorithm to compute a dominating path in an AT-free graph
- An O(N + M)-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
- Asteroidal Triple-Free Graphs
- Clustering and domination in perfect graphs
- Complexity of Finding Embeddings in a k-Tree
- Computing the Minimum Fill-In is NP-Complete
- Connected domination and steiner set on asteroidal triple-free graphs
- Dominating sets in perfect graphs
- Domination in permutation graphs
- Domination on Cocomparability Graphs
- Domination, independent domination, and duality in strongly chordal graphs
- scientific article; zbMATH DE number 3859178 (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?)
- Independence and domination in polygon graphs
- Independent sets in asteroidal triple-free graphs
- Introduction to ``Topics on Domination
- Labeling algorithms for domination problems in sun-free chordal graphs
- Linear time algorithms for dominating pairs in asteroidal triple-free graphs
- On Hadwiger's Number and the Stability Number
- The complexity of domination problems in circle graphs
- The NP-completeness column: An ongoing guide
- Total domination and transformation
- Efficient algorithms for Roman domination on some classes of graphs
- A generalization of AT-free graphs and a generic algorithm for solving triangulation problems
- Algorithms for graphs with small octopus
- On claw-free asteroidal triple-free graphs
- Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes
- Complexity of paired domination in AT-free and planar graphs
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- On the minimum eccentricity shortest path problem
- On the structure of graphs with bounded asteroidal number
- Edge-dominating trails in AT-free graphs (extended abstract)
- Vertex ranking of asteroidal triple-free graphs
- A complexity dichotomy and a new boundary class for the dominating set problem
- On the minimum eccentricity shortest path problem
- Independent Sets in Asteroidal Triple-Free Graphs
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Asteroidal Triple-Free Graphs
- Independent sets in asteroidal triple-free graphs
- Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs
- On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
- Connected domination and steiner set on asteroidal triple-free graphs
- scientific article; zbMATH DE number 7511525 (Why is no real title available?)
- Domination problems on \(P_{5}\)-free graphs
- On the structure of graphs with bounded asteroidal number
- The diameter of AT‐free graphs
- Complexity of paired domination in at-free and planar graphs
- Connected feedback vertex set on AT-free graphs
- On conditional covering problem
- Asteroidal sets and dominating paths
- Connected feedback vertex set on AT-free graphs
- A linear time algorithm to compute a dominating path in an AT-free graph
- Connected vertex cover on AT-free graphs
- Subset feedback vertex set and subset vertex cover on AT-free graphs
- Outer-planar vertex deletion on AT-free graphs
- Semitotal domination on AT-free graphs and circle graphs
- Matching properties in total domination vertex critical graphs
- A survey of selected recent results on total domination in graphs
This page was built for publication: Domination and total domination on asteroidal triple-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1962038)
