Fast algorithms for the dominating set problem on permutation graphs

DOI10.1007/BF01190158zbMath0768.68063OpenAlexW2060838596MaRDI QIDQ2366239

Yanyan Li

Publication date: 29 June 1993

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01190158

zbMATH Keywords

dynamic programmingdata structurespermutation graphsdominating set problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items (6)

An efficient algorithm to solve the distancek-domination problem on permutation graphs ⋮ Graph classes with structured neighborhoods and algorithmic applications ⋮ A polynomial-time algorithm for the paired-domination problem on permutation graphs ⋮ An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs ⋮ Graph Classes with Structured Neighborhoods and Algorithmic Applications ⋮ Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs

Cites Work

• On domination problems for permutation and other graphs
• Finding a minimum independent dominating set in a permutation graph
• Preserving order in a forest in less than logarithmic time and linear space
• Domination in permutation graphs

This page was built for publication: Fast algorithms for the dominating set problem on permutation graphs