Name
Abstract | ||
|---|---|---|
Given an integer k , k ≥3, we define the class of k -polygon graphs to be the intersection graphs of straight-line chords inside a convex k -gon. Thus, permutation graphs form a proper subset of any such class. Moreover, circle graphs = ∪ ∞ k =3 k -polygon graphs. In this paper, we show polynomial time exact algorithms for solving the maximum r -independent set problem (finding a maximum subset of vertices that can be partitioned into r independent sets) and the minimum dominating set problem on k -polygen graphs, for any fixed k . |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1016/0166-218X(93)90222-A | Discrete Applied Mathematics |
Keywords | Field | DocType |
polygon graph | Permutation graph,Discrete mathematics,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Pathwidth,Trapezoid graph,Mathematics,Metric dimension,Maximal independent set | Journal |
Volume | Issue | ISSN |
44 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
9 | 0.62 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehab S. Elmallah | 1 | 105 | 19.29 |
| Lorna K. Stewart | 2 | 320 | 39.39 |