Name
Abstract | ||
|---|---|---|
In this paper we prove some basic properties of the g-centroid of a graph defined through g-convexity. We also prove that finding the g-centroid of a graph is NP-hard by reducing the problem of finding the maximum clique size of G to the g-centroidal problem. We give an O(n(2)) algorithm for finding the g-centroid for maximal outer planar graphs, an O(m + nlogn) time algorithm for split graphs and an O(m(2)) algorithm for ptolemaic graphs. For split graphs and ptolemaic graphs we show that the g-centroid is in fact a complete subgraph. |
Year | Venue | Keywords |
|---|---|---|
1998 | ARS COMBINATORIA | perfect graph |
Field | DocType | Volume |
Perfect graph,Discrete mathematics,Indifference graph,Combinatorics,Chordal graph,Cograph,Trivially perfect graph,Mathematics,Perfect graph theorem,Split graph,Strong perfect graph theorem | Journal | 50 |
ISSN | Citations | PageRank |
0381-7032 | 3 | 0.52 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. Pandu Rangan | 1 | 1434 | 149.57 |
| K. R. Parthasarathy | 2 | 12 | 2.64 |
| V. Prakash | 3 | 4 | 1.23 |