Next Article in Journal
The Parameterized Complexity of the Rainbow Subgraph Problem
Previous Article in Journal
An Efficient SAR Image Segmentation Framework Using Transformed Nonlocal Mean and Multi-Objective Clustering in Kernel Space
Article

Recognition of Unipolar and Generalised Split Graphs

1
Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, United Kingdom
2
Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX 13QD, United Kingdom
*
Author to whom correspondence should be addressed.
Academic Editor: Abu-Khzam Faisal
Received: 4 July 2014 / Accepted: 26 January 2015 / Published: 13 February 2015
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. View Full-Text
Keywords: unipolar graphs, generalised split graphs, perfect graphs, recognition algorithms, representations unipolar graphs, generalised split graphs, perfect graphs, recognition algorithms, representations
Show Figures

MDPI and ACS Style

McDiarmid, C.; Yolov, N. Recognition of Unipolar and Generalised Split Graphs. Algorithms 2015, 8, 46-59. https://0-doi-org.brum.beds.ac.uk/10.3390/a8010046

AMA Style

McDiarmid C, Yolov N. Recognition of Unipolar and Generalised Split Graphs. Algorithms. 2015; 8(1):46-59. https://0-doi-org.brum.beds.ac.uk/10.3390/a8010046

Chicago/Turabian Style

McDiarmid, Colin; Yolov, Nikola. 2015. "Recognition of Unipolar and Generalised Split Graphs" Algorithms 8, no. 1: 46-59. https://0-doi-org.brum.beds.ac.uk/10.3390/a8010046

Find Other Styles

Article Access Map by Country/Region

1
Only visits after 24 November 2015 are recorded.
Search more from Scilit
 
Search
Back to TopTop