Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/25631

Title: Sorting by reversals and the theory of 4-regular graphs
Authors: Brijder, Robert
Issue Date: 2017
Citation: Theoretical computer science, 701, p. 40-53
Abstract: We show that the theory of sorting by reversals fits into the well-established theory of circuit partitions of 4-regular multigraphs (which also involves the combinatorial structures of circle graphs and delta-matroids). In this way, we expose strong connections between the two theories that have not been fully appreciated before. We also discuss a generalization of sorting by reversals involving the double-cut-and-join (DCJ) operation. Finally, we also show that the theory of sorting by reversals is closely related to that of gene assembly in ciliates.
URI: http://hdl.handle.net/1942/25631
DOI: 10.1016/j.tcs.2017.02.033
ISI #: 000418969500007
ISSN: 0304-3975
Category: A1
Type: Journal Contribution
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Published version629.85 kBAdobe PDF
Non peer-reviewed author version358.68 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.