4 papers
Decomposing time-varying data into simple pieces: structured decompositions of narratives
Benjamin Merlin Bumpus, Jana K. Nickel
Graphs that change over time arise throughout applications, but there is no single standard way to decompose them into smaller pieces. In this paper, we propose a systematic catego…
Locally interval graphs are circular-arc graphs
Tara Abrishami, Sandra Albrechtsen, Nathan Bowler +2
Circular-arc graphs are graphs that can be represented as intersection graphs of subpaths of a cycle. Interval graphs are graphs that can be represented as intersection graphs of s…
A generalisation of Menger's theorem in bidirected graphs
Ebrahim Ghorbani, Jana Katharina Nickel, Florian Reich
Menger's theorem - the maximum number of vertex-disjoint - paths is equal to the minimum size of an - separator - is generally not true in bidirected graphs. We prove t…
Disjoint -paths in bidirected graphs
Jana K. Nickel
Let be a bidirected multigraph with signing , let be a set of vertices in , and let be a non-negative integer. For any pair of vertex sets sati…