An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph

DOI10.1137/S0097539794200383zbMath0851.68089OpenAlexW2022850650MaRDI QIDQ4877526

Y. Daniel Liang, S. Lakshmivarahan, Chongkye Rhee, Sudarshan K. Dhall

Publication date: 10 November 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794200383

zbMATH Keywords

dominating setpermutation graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

Total domination and transformation, On the feedback vertex set problem in permutation graphs, Dominations in trapezoid graphs, An efficient algorithm to solve the distancek-domination problem on permutation graphs, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, Graph classes with structured neighborhoods and algorithmic applications, Domination and total domination on asteroidal triple-free graphs, Incorporating negative-weight vertices in certain vertex-search graph algorithms, An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs, Graph Classes with Structured Neighborhoods and Algorithmic Applications