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

Actions


Access Document


Files:
Publisher copy:
10.3390/a8010046

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Statistics
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
MDPI Publisher's website
Journal:
Algorithms Journal website
Volume:
8
Issue:
1
Pages:
46-59
Publication date:
2015-01-01
Acceptance date:
2015-01-26
DOI:
EISSN:
1999-4893
Source identifiers:
516524
Keywords:
Pubs id:
pubs:516524
UUID:
uuid:103b8ac5-a97f-4679-95a8-f19ef0947f3f
Local pid:
pubs:516524
Deposit date:
2016-03-01

Terms of use


Views and Downloads






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

TO TOP