Computing a dominating pair in an asteroidal triple-free graph in linear time

DOI10.1007/3-540-60220-8_76MaRDI QIDQ5057448zbMATH OpenOpenAlexFDO

Authors Stephan Olariu, Derek G. Corneil, Lorna Stewart

Publication date 16 December 2022

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

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

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Connected domination and steiner set on asteroidal triple-free graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• A linear time algorithm to compute a dominating path in an AT-free graph
• Asteroidal Triple-Free Graphs

Cites work

• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A linear time algorithm to compute a dominating path in an AT-free graph
• Asteroidal Triple-Free Graphs
• Connected domination and steiner set on asteroidal triple-free graphs
• Domination on Cocomparability Graphs
• Graph theory with applications
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4063148 (Why is no real title available?)
• scientific article; zbMATH DE number 3767009 (Why is no real title available?)
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Partial orders of dimension 2
• Permutation Graphs and Transitive Graphs
• Representation of a finite graph by a set of intervals on the real line
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Tolerance graphs
• Trapezoid graphs and their coloring

Cited in

(13)

• Hereditary dominating pair graphs
• Convex and isometric domination of (weak) dominating pair graphs
• Domination and total domination on asteroidal triple-free graphs
• Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
• Asteroidal Triple-Free Graphs
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• Dominating Pair Graphs
• scientific article; zbMATH DE number 7511525 (Why is no real title available?)
• On the structure of graphs with bounded asteroidal number
• Connected feedback vertex set on AT-free graphs
• 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

This page was built for publication: Computing a dominating pair in an asteroidal triple-free graph in linear time

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