TY - JOUR

T1 - An O(m=n) Algorithm for Finding a Minimum Weight Dominating Set in Permutation Graphs

AU - Rhee, C.

AU - Liang, Y. D.

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

N1 - (2013) An -time algorithm for the paired domination problem on permutation graphs. European Journal of Combinatorics 34:3, 593-608. 2011. Efficient Algorithms to Solve k-Domination Problem on Permutation Graphs. High Performance Networking, Computing, and Communication Systems, 327-334. 2011. Graph Classes with Structured Neighborhoods and Algorithmic Applications. Graph-Theoretic Concepts in Computer Science, 47-58.

PY - 1996

Y1 - 1996

N2 - Farber and Keil [Algorithmica, 4 (1989), pp. 221–236] presented an $O(n^3 )$-time algorithm for finding a minimum-weight dominating set in permutation graphs. This result was improved to $O(n^2 \log ^2 n)$ by Tsai and Hsu [SIGAL ’90 Algorithms, Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 109–117] and to $O(n(n + m)$ by the authors of this paper [Inform. Process. Lett., 37 (1991), pp. 219–224], respectively. In this paper, we introduce a new faster algorithm that takes only $O(n + m)$ time to solve the same problem, where m is the number of edges in a graph of n vertice Read More: https://epubs.siam.org/doi/abs/10.1137/S0097539794200383?journalCode=smjcat

AB - Farber and Keil [Algorithmica, 4 (1989), pp. 221–236] presented an $O(n^3 )$-time algorithm for finding a minimum-weight dominating set in permutation graphs. This result was improved to $O(n^2 \log ^2 n)$ by Tsai and Hsu [SIGAL ’90 Algorithms, Lecture Notes in Computer Science, Springer-Verlag, New York, 1990, pp. 109–117] and to $O(n(n + m)$ by the authors of this paper [Inform. Process. Lett., 37 (1991), pp. 219–224], respectively. In this paper, we introduce a new faster algorithm that takes only $O(n + m)$ time to solve the same problem, where m is the number of edges in a graph of n vertice Read More: https://epubs.siam.org/doi/abs/10.1137/S0097539794200383?journalCode=smjcat

UR - https://epubs.siam.org/doi/10.1137/S0097539794200383

U2 - 10.1137/S0097539794200383

DO - 10.1137/S0097539794200383

M3 - Article

SN - 0097-5397

VL - 25

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

ER -