Linear time algorithms for dominating pairs in asteroidal triple-free graphs

DOI10.1007/3-540-60084-1_82zbMath1415.05130OpenAlexW1595794833MaRDI QIDQ4645186

Stephan Olariu, Lorna K. Stewart, Derek Gordon Corneil

Publication date: 10 January 2019

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60084-1_82

Mathematics Subject Classification ID

Analysis of algorithms (68W40) 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

An approximation algorithm for clustering graphs with dominating diametral path, On the Minimum Eccentricity Shortest Path Problem, Computing a dominating pair in an asteroidal triple-free graph in linear time, Complexity of paired domination in AT-free and planar graphs, Independent sets in asteroidal triple-free graphs, On the minimum eccentricity shortest path problem, On treewidth and minimum fill-in of asteroidal triple-free graphs, Complexity of paired domination in at-free and planar graphs, Domination and total domination on asteroidal triple-free graphs, Efficient algorithms for Roman domination on some classes of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm to compute a dominating path in an AT-free graph
• Tolerance graphs
• Trapezoid graphs and their coloring
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Domination on Cocomparability Graphs
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• Connected domination and steiner set on asteroidal triple-free graphs
• Partial orders of dimension 2
• Permutation Graphs and Transitive Graphs