1 citations · 1 across the 11 of their papers we have counts for
19 papers
Snapshot disjointness in temporal graphs
Allen Ibiapina, Ana Silva
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness were proposed over the years, and the val…
Mengerian graphs: characterization and recognition
Allen Ibiapina, Ana Silva
A temporal graph is a graph that changes with time. More specifically, it is a pair where is a graph and is a function on the edges of that describe…
Revising Johnson's table for the 21st century
Celina M. H. de Figueiredo, Alexsander A. de Melo, Diana Sasaki +1
What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 "Graph Restrictions and Their Effect" of D. S.…
Königsberg Sightseeing: Eulerian Walks in Temporal Graphs
Andrea Marino, Ana Silva
An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph at least (resp. exactly) once. This notion was first discussed by Leonhard Euler…
Maximum cut on interval graphs of interval count four is NP-complete
Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira +1
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80's, being one of the problems proposed by Johnson on his Ongoing Guide to…
A Unifying Model for Locally Constrained Spanning Tree Problems
Luiz Alberto do Carmo Viana, Manoel Campêlo, Ignasi Sau +1
Given a graph and a digraph whose vertices are the edges of , we investigate the problem of finding a spanning tree of that satisfies the constraints imposed by .…