A New Approach for the Domination Problem on Permutation Graphs

Y. Liang; C. Rhee; S. K. Dhall; S. Lakshmivarahan

doi:10.1016/0020-0190(91)90192-K

A New Approach for the Domination Problem on Permutation Graphs

Y. Liang, C. Rhee, S. K. Dhall, S. Lakshmivarahan

Computer Science

University of Oklahoma

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

Farber and Keil presented an O( n 3 algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n ( m + n )) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.

Original language	American English
Journal	Information Processing Letters
Volume	37
DOIs	https://doi.org/10.1016/0020-0190(91)90192-K
State	Published - Feb 28 1991

Disciplines

Computer Sciences

Keywords

Algorithm analysis
minimum weight dominating set
permutation graph

Access to Document

10.1016/0020-0190(91)90192-KLicense: Unspecified

Cite this

@article{663db3f224d14d888c61611daec2df0e,

title = "A New Approach for the Domination Problem on Permutation Graphs",

abstract = " Farber and Keil presented an O( n 3 algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n ( m + n )) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs. ",

keywords = "Algorithm analysis, minimum weight dominating set, permutation graph",

author = "Y. Liang and C. Rhee and Dhall, \{S. K.\} and S. Lakshmivarahan",

note = "Farber and Keil presented an O( algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n( m+ n)) steps, where m is the number of edges in a permutation graph G of n nodes.",

year = "1991",

month = feb,

day = "28",

doi = "10.1016/0020-0190(91)90192-K",

language = "American English",

volume = "37",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - A New Approach for the Domination Problem on Permutation Graphs

AU - Liang, Y.

AU - Rhee, C.

AU - Dhall, S. K.

AU - Lakshmivarahan, S.

N1 - Farber and Keil presented an O( algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n( m+ n)) steps, where m is the number of edges in a permutation graph G of n nodes.

PY - 1991/2/28

Y1 - 1991/2/28

N2 - Farber and Keil presented an O( n 3 algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n ( m + n )) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.

AB - Farber and Keil presented an O( n 3 algorithm for finding a minimum weight dominating set on permutation graphs. In this paper, we take a new approach for solving the same problem. The algorithm takes O( n ( m + n )) steps, where m is the number of edges in a permutation graph G of n nodes. Therefore, our algorithm is particularly good for the sparse permutation graphs.

KW - Algorithm analysis

KW - minimum weight dominating set

KW - permutation graph

UR - https://www.sciencedirect.com/science/article/pii/002001909190192K

U2 - 10.1016/0020-0190(91)90192-K

DO - 10.1016/0020-0190(91)90192-K

M3 - Article

SN - 0020-0190

VL - 37

JO - Information Processing Letters

JF - Information Processing Letters

ER -

A New Approach for the Domination Problem on Permutation Graphs

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this