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 -