1 citations · 1 across the 5 of their papers we have counts for
5 papers
Randomization Helps in Online Graph Exploration: Breaking the Deterministic Lower Bound on Cycles
Júlia Baligács, Jan Hązła, Lena Volk
In online graph exploration, introduced by Kalyanasundaram and Pruhs (1994), an agent must visit all vertices of an initially unknown weighted graph and return to its starting posi…
On Edge-Disjoint Maximal Outerplanar Graphs
Yuto Okada, Yota Otachi, Lena Volk
We provide two constructions for edge-disjoint maximal outerplanar graphs on every number of vertices. The bound on the minimum number of vertices is tight. These c…
Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
Tesshu Hanaka, Yuto Okada, Yota Otachi +1
We study the parameterized complexity of the problems of finding a maximum common (induced) subgraph of two given graphs. Since these problems generalize several NP-complete proble…
Symmetry classes of Hamiltonian cycles
Julia Baligacs, Sofia Brenner, Annette Lutz +1
We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs…
On the twin-width of near-regular graphs
Irene Heinrich, Ferdinand Ihringer, Simon Raßmann +1
Twin-width is a recently introduced graph parameter based on the repeated contraction of near-twins. It has shown remarkable utility in algorithmic and structural graph theory, as…