Home
Department of Informatics
Informatics | Department Seminar

A Kid Krypto System based on DIRECTED CYCLE COVER

We are pleased to have Frances Rosamond speak at this next Department Seminar.

Main content

ABSTRACT

The DIRECTED CYCLE COVER (DCC) problem asks, for input a digraph D = {V, A} whether there exists a family F = {C 1, …, Cm} vertex-disjoint directed cycles that “spans D”, that is, for every v in V there is a unique directed cycle of F that passes through V. This is an NP-hard problem. 

The talk will describe how this NP-hard combinatorial problem can serve as the basis for a “Kid Krypto” PKCS. The main (only) such construction so far has been the PERFECT CODE problem. Both of the PERFECT CODE and DIRECTED CYCLE COVER based Kid Krypto PKCSs can be cracked with linear algebra—but this still leaves them appropriate for young audiences in the general project of communicating contemporary mathematical science, and important project that will be touched upon.

 

About Frances Rosamond, Ph.D

Affiliation: Rosamond Computer Science, Research and Education company Bergen, Norway

Frances Rosamond has her Ph.D. from Cornell University, Ithaca, NY. She comes to Bergen, Norway after being Professor of Computer Science at Charles Darwin University, Northern Territory, Australia, and at University of Newcastle, Australia. Before coming to Australia, she was the inaugural department chair of Mathematics and Natural Sciences of National University, San Diego, California. She is the Editor of the Parameterized Complexity Newsetter and wiki (www.fpt.wikidot.com), and chairs the Steering Committee for PACE, the newly formed Parameterized Algorithms and Computational Experiments Challenge. In addition to parameterized/multivariate algorithmics research, Frances and her husband Mike Fellows are involved in computer-math outreach. She started the Creative Mathematical Sciences Communication (CMSC) conference series to popularize and interest researchers in developing “Computer Science Unplugged” activities.