Name
Abstract | ||
|---|---|---|
A graph is unipolar if it can be partitioned into a clique and a disjoint union of cliques, and a graph is a generalised split graph if it or its complement is unipolar. A unipolar partition of a graph can be used to find efficiently the clique number, the stability number, the chromatic number, and to solve other problems that are hard for general graphs. We present an O(n(2))-time algorithm for recognition of n-vertex generalised split graphs, improving on previous O(n(3))-time algorithms. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.3390/a8010046 | ALGORITHMS |
Keywords | Field | DocType |
generalised split graphs,perfect graphs,recognition algorithms,representations,unipolar graphs | Block graph,Discrete mathematics,Combinatorics,Line graph,Clique-sum,Chordal graph,Cograph,Treewidth,Pathwidth,Mathematics,Split graph | Journal |
Volume | Issue | ISSN |
8 | 1 | 1999-4893 |
Citations | PageRank | References |
5 | 0.65 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin McDiarmid | 1 | 1071 | 167.05 |
| Nikola Yolov | 2 | 7 | 2.05 |