![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
On the Smallest Synchronizing Terms of Finite Tree Automata
This paper deals with properties of synchronizing terms for finite tree automata, which is a generalization of the synchronization principle of deterministic finite string automata (DFA) and such terms correspond...
-
Chapter and Conference Paper
Correction to: Bears with Hats and Independence Polynomials
Chapter [“Bears with Hats and Independence Polynomials”] was previously published non-open access. It has now been changed to open access under a CC BY 4.0 license and the copyright holder updated to ‘The Auth...
-
Chapter and Conference Paper
Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set
Consider a vertex-weighted graph G with a source s and a target t. Tracking Paths requires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path from s to t is unique...
-
Chapter and Conference Paper
Bears with Hats and Independence Polynomials
Consider the following hat guessing game. A bear sits on each vertex of a graph G, and a demon puts on each bear a hat colored by one of h colors. Each bear sees only the hat colors of his neighbors. Based on thi...
-
Chapter and Conference Paper
On the Intersections of Non-homotopic Loops
Let \(V = \{v_1, \dots , v_n\}\) V = ...
-
Chapter and Conference Paper
Non-homotopic Loops with a Bounded Number of Pairwise Intersections
Let \(V_n\) V n ...
-
Chapter and Conference Paper
On the Edge-Length Ratio of 2-Trees
We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88–94] and,...
-
Chapter and Conference Paper
On the m-eternal Domination Number of Cactus Graphs
Given a graph G, guards are placed on vertices of G. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal do...
-
Chapter and Conference Paper
On Induced Online Ramsey Number of Paths, Cycles, and Trees
An online Ramsey game is a game between Builder and Painter, alternating in turns. They are given a fixed graph H and a an infinite set of independent vertices G. In each round Builder draws a new edge in G and P...
-
Chapter and Conference Paper
A Simple Streaming Bit-Parallel Algorithm for Swap Pattern Matching
The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allowing the pattern to swap adjacent symbols. The goal is to design fast matching algorithm that takes advantage...