Recognition of Unipolar and Generalised Split Graphs
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2015-02-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/8/1/46 |
| _version_ | 1828351581192454144 |
|---|---|
| author | Colin McDiarmid Nikola Yolov |
| author_facet | Colin McDiarmid Nikola Yolov |
| author_sort | Colin McDiarmid |
| collection | DOAJ |
| description | 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(n2)-time algorithm for recognition of n-vertex generalised split graphs, improving on previous O(n3)-time algorithms. |
| first_indexed | 2024-04-14T01:41:12Z |
| format | Article |
| id | doaj.art-342a351cb4294b0e93e6f551e8ddf8f3 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-14T01:41:12Z |
| publishDate | 2015-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-342a351cb4294b0e93e6f551e8ddf8f32022-12-22T02:19:43ZengMDPI AGAlgorithms1999-48932015-02-0181465910.3390/a8010046a8010046Recognition of Unipolar and Generalised Split GraphsColin McDiarmid0Nikola Yolov1Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, United KingdomDepartment of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX 13QD, United KingdomA 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(n2)-time algorithm for recognition of n-vertex generalised split graphs, improving on previous O(n3)-time algorithms.http://www.mdpi.com/1999-4893/8/1/46unipolar graphs, generalised split graphs, perfect graphs, recognition algorithms, representations |
| spellingShingle | Colin McDiarmid Nikola Yolov Recognition of Unipolar and Generalised Split Graphs Algorithms unipolar graphs, generalised split graphs, perfect graphs, recognition algorithms, representations |
| title | Recognition of Unipolar and Generalised Split Graphs |
| title_full | Recognition of Unipolar and Generalised Split Graphs |
| title_fullStr | Recognition of Unipolar and Generalised Split Graphs |
| title_full_unstemmed | Recognition of Unipolar and Generalised Split Graphs |
| title_short | Recognition of Unipolar and Generalised Split Graphs |
| title_sort | recognition of unipolar and generalised split graphs |
| topic | unipolar graphs, generalised split graphs, perfect graphs, recognition algorithms, representations |
| url | http://www.mdpi.com/1999-4893/8/1/46 |
| work_keys_str_mv | AT colinmcdiarmid recognitionofunipolarandgeneralisedsplitgraphs AT nikolayolov recognitionofunipolarandgeneralisedsplitgraphs |