Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring [PDF]
TheoretiCS, 2023 Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model.
Sepehr Assadi +2 more
doaj +1 more source
Fast Diameter Computation within Split Graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two.
Guillaume Ducoffe +2 more
doaj +1 more source
On-line algorithms for multiplication and division in real and complex numeration systems [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 A positional numeration system is given by a base and by a set of digits. The base is a real or complex number $\beta$ such that $|\beta|>1$, and the digit set $A$ is a finite set of digits including $0$. Thus a number can be seen as a finite or infinite
Christiane Frougny +3 more
doaj +1 more source
Data Structures and Algorithms [PDF]
Scientific American, 1984 ETH, Eidgenössische Technische Hochschule Zürich, Institut für Informatik ...
Wirth, Niklaus, Gutknecht, Jürg
openaire +2 more sources
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called \BVA). An input of this problem is defined by $m$ disjoint sets $V^1, V^2, \dots, V^m$, each composed of $n$ binary vectors of size $
Marin Bougeret +3 more
doaj +1 more source
Evacuating Robots from a Disk Using Face-to-Face Communication [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk.
Jurek Czyzowicz +5 more
doaj +1 more source
THE ROLE OF METHODOLGY IN PEDAGOGICAL RESEARCH IN TERMS OF IMPROVING SKILLS OF HIGH SCHOOL STUDENTS PROGRAMMING [PDF]
Journal of International Legal Communication, 2021 This paper presents analysis of learning and programming skills of students in High School, course computer technician. Students from all grades participated in the research.
Linda Jurakovic +2 more
doaj +1 more source
Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models [PDF]
Discrete Mathematics & Theoretical Computer Science, 2019 We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A
Konstantinos Georgiou +2 more
doaj +1 more source
Longest Gapped Repeats and Palindromes [PDF]
Discrete Mathematics & Theoretical Computer Science, 2017 A gapped repeat (respectively, palindrome) occurring in a word $w$ is a factor $uvu$ (respectively, $u^Rvu$) of $w$. In such a repeat (palindrome) $u$ is called the arm of the repeat (respectively, palindrome), while $v$ is called the gap. We show how to
Marius Dumitran +2 more
doaj +1 more source
New Results on Directed Edge Dominating Set [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 We study a family of generalizations of Edge Dominating Set on directed graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc $(u,v)$ is said to dominate itself, as well as all arcs which are at distance at most $q$ from $v$, or at ...
Rémy Belmonte +4 more
doaj +1 more source