Source author record

Olli Pottonen

Olli Pottonen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Information Theory math.IT Computational Complexity

Catalog footprint

What is connected

6works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Complexity of Metric Dimension on Planar Graphs

The metric dimension of a graph $G$ is the size of a smallest subset $L \subseteq V(G)$ such that for any $x,y \in V(G)$ with $x\not= y$ there is a $z \in L$ such that the graph distance between $x$ and $z$ differs from the graph distance between $y$ and $z$. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree $6$ is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.

preprint2014arXiv

Non-existence of a ternary constant weight $(16, 5, 15; 2048)$ diameter perfect code

Ternary constant weight codes of length $n=2^m$, weight $n-1$, cardinality $2^n$ and distance $5$ are known to exist for every $m$ for which there exists an APN permutation of order $2^m$, that is, at least for all odd $m \geq 3$ and for $m=6$. We show the non-existence of such codes for $m=4$ and prove that any codes with the parameters above are diameter perfect.

preprint2011arXiv

On Optimal Binary One-Error-Correcting Codes of Lengths $2^m-4$ and $2^m-3$

Best and Brouwer [Discrete Math. 17 (1977), 235-245] proved that triply-shortened and doubly-shortened binary Hamming codes (which have length $2^m-4$ and $2^m-3$, respectively) are optimal. Properties of such codes are here studied, determining among other things parameters of certain subcodes. A utilization of these properties makes a computer-aided classification of the optimal binary one-error-correcting codes of lengths 12 and 13 possible; there are 237610 and 117823 such codes, respectively (with 27375 and 17513 inequivalent extensions). This completes the classification of optimal binary one-error-correcting codes for all lengths up to 15. Some properties of the classified codes are further investigated. Finally, it is proved that for any $m \geq 4$, there are optimal binary one-error-correcting codes of length $2^m-4$ and $2^m-3$ that cannot be lengthened to perfect codes of length $2^m-1$.

preprint2011arXiv

Two Optimal One-Error-Correcting Codes of Length 13 That Are Not Doubly Shortened Perfect Codes

The doubly shortened perfect codes of length 13 are classified utilizing the classification of perfect codes in [P.R.J. Östergård and O. Pottonen, The perfect binary one-error-correcting codes of length 15: Part I - Classification, IEEE Trans. Inform. Theory, to appear]; there are 117821 such (13,512,3) codes. By applying a switching operation to those codes, two more (13,512,3) codes are obtained, which are then not doubly shortened perfect codes.

preprint2010arXiv

The Perfect Binary One-Error-Correcting Codes of Length 15: Part II--Properties

A complete classification of the perfect binary one-error-correcting codes of length 15 as well as their extensions of length 16 was recently carried out in [P. R. J. Östergård and O. Pottonen, "The perfect binary one-error-correcting codes of length 15: Part I--Classification," IEEE Trans. Inform. Theory vol. 55, pp. 4657--4660, 2009]. In the current accompanying work, the classified codes are studied in great detail, and their main properties are tabulated. The results include the fact that 33 of the 80 Steiner triple systems of order 15 occur in such codes. Further understanding is gained on full-rank codes via switching, as it turns out that all but two full-rank codes can be obtained through a series of such transformations from the Hamming code. Other topics studied include (non)systematic codes, embedded one-error-correcting codes, and defining sets of codes. A classification of certain mixed perfect codes is also obtained.

preprint2009arXiv

The Perfect Binary One-Error-Correcting Codes of Length 15: Part I--Classification

A complete classification of the perfect binary one-error-correcting codes of length 15 as well as their extensions of length 16 is presented. There are 5983 such inequivalent perfect codes and 2165 extended perfect codes. Efficient generation of these codes relies on the recent classification of Steiner quadruple systems of order 16. Utilizing a result of Blackmore, the optimal binary one-error-correcting codes of length 14 and the (15, 1024, 4) codes are also classified; there are 38408 and 5983 such codes, respectively.