Open AccessWeighted independent perfect domination on cocomparability graphs
Author(s) -
Gerard J. Chang,
C. Pandu Rangan,
S. Coorg
Publication year - 1993
Publication title -
lecture notes in computer science
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 0.249
H-Index - 400
eISSN - 1611-3349
pISSN - 0302-9743
DOI - 10.1007/3-540-57568-5_282
Subject(s) - combinatorics , vertex (graph theory) , interval graph , graph , maximal independent set , mathematics , chordal graph , computer science , discrete mathematics , 1 planar graph
Suppose G=(V,E) is a graph in which every vertex v ∃ V is associated with a cost c(v). This paper studies the weighted independent perfect domination problem on G, i.e., the problem of finding a subset D of V such that every vertex in V is equal or adjacent to exactly one vertex in D and σ{c(v): v ∃ D is minimum. We give an O(¦V∥E¦) algorithm for the problem on cocomparability graphs. The algorithm can be implemented to run in O(¦V¦2.37) time. With some modifications, the algorithm yields an O(¦V¦ + ¦E¦) algorithm on interval graphs, which are special cocomparability graphs.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom