Journal article icon

Journal article

Recognition of unipolar and generalised split graphs

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(n2)-time algorithm for recognition of n-vertex generalised split graphs, improving on previous O(n3)-time algorithms.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Publisher's version

Actions


Access Document


Files:
Publisher copy:
10.3390/a8010046

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Statistics
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Publisher:
MDPI Publisher's website
Journal:
Algorithms Journal website
Volume:
8
Issue:
1
Pages:
46-59
Publication date:
2015
DOI:
EISSN:
1999-4893
URN:
uuid:103b8ac5-a97f-4679-95a8-f19ef0947f3f
Source identifiers:
516524
Local pid:
pubs:516524

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP