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

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

McDiarmid, C., & Yolov, N. (2015). Recognition of unipolar and generalised split graphs. Algorithms, 8(1), 46–59.

MLA Style

McDiarmid, C, and N Yolov. “Recognition of Unipolar and Generalised Split Graphs.” Algorithms, vol. 8, no. 1, 2015, pp. 46–59.

Chicago Style

McDiarmid, C, and N Yolov. 2015. “Recognition of Unipolar and Generalised Split Graphs.” Algorithms 8 (1): 46–59.
Print

Access Document

Files:: McDiarmid_and_Yolov_2015_Recognition_of_unipolar.pdf

(Preview, Version of record, pdf, 263.1KB, Terms of use)

Publisher copy:: 10.3390/a8010046

Authors

+ McDiarmid, C More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Statistics
Role:: Author

+ Yolov, N More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Engineering and Physical Sciences Research Council More from this funder

Funding agency for:: Yolov, N

Publisher:: MDPI
Journal:: Algorithms More from this journal
Volume:: 8
Issue:: 1
Pages:: 46-59
Publication date:: 2015-02-13
Acceptance date:: 2015-01-26
DOI:: 10.3390/a8010046
EISSN:: 1999-4893

Language:: English
Keywords:: generalised split graphs

unipolar graphs

representations

recognition algorithms

perfect graphs
Pubs id:: pubs:516524
UUID:: uuid:103b8ac5-a97f-4679-95a8-f19ef0947f3f
Local pid:: pubs:516524
Source identifiers:: 516524
Deposit date:: 2016-03-01
ARK identifier:: ark:/29072/ora_103b8ac5a97f467995a8f19ef0947f3f

Terms of use

Copyright holder:: McDiarmid and Yolov
Copyright date:: 2015
Rights statement:: Copyright © 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/)

Licence:: CC Attribution (CC BY)

Views and Downloads

About 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