Back to Search
Start Over
Successful Pressing Sequences for a Bicolored Graph and Binary Matrices
- Publication Year :
- 2015
-
Abstract
- We apply matrix theory over F 2 to understand the nature of so-called “successful pressing sequences” of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work.
- Subjects :
- Pressing
Numerical Analysis
05C50, 15B33, 92D15
Algebra and Number Theory
010102 general mathematics
Binary number
0102 computer and information sciences
01 natural sciences
Graph
Combinatorics
010201 computation theory & mathematics
Computational phylogenetics
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
Logical matrix
Combinatorics (math.CO)
Geometry and Topology
Adjacency matrix
0101 mathematics
Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....591074f6fa91da70ff8e2e25a2ee5928