From the 1 of 5 linked papers with an AI index.
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
The paper presents a randomized algorithm for online exploration of cycle graphs that achieves a competitive ratio of at most 1.315, surpassing the best possible deterministic rati…
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 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…
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…