Cover Image

The Power of Graph Doubling: Computing Ultrabubbles in a Bidirected Graph by Reducing to Weak Superbubbles

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Schmidt, Sebastian, Harviainen, Juha, Moumard, Corentin, Politov, Aleksandr, Sena, Francisco, Tomescu, Alexandru I.
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms F.2.2; J.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework
by: Sena, Francisco, et al.
Published: (2025)

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree framework
by: Sena, Francisco, et al.
Published: (2026)

Near-Linear Time Computation of Welzl Orders on Graphs with Linear Neighborhood Complexity
by: Dreier, Jan, et al.
Published: (2026)

Fast and Flexible Flow Decompositions in General Graphs via Dominators
by: Sena, Francisco, et al.
Published: (2025)

Graph Threading
by: Demaine, Erik D., et al.
Published: (2023)

Simpler and Unified Recognition Algorithm for Path Graphs and Directed Path Graphs
by: Balzotti, Lorenzo
Published: (2020)

Bidirectional Dijkstra's Algorithm is Instance-Optimal
by: Haeupler, Bernhard, et al.
Published: (2024)

Graph Reconstruction with a Connected Components Oracle
by: Harviainen, Juha, et al.
Published: (2025)

Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
by: Ahn, Jungho, et al.
Published: (2025)

On Hardness and Approximation of Broadcasting in Structured Graphs
by: Bringolf, Jeffrey, et al.
Published: (2025)

Colorful Vertex Recoloring of Bipartite Graphs
by: Patt-Shamir, Boaz, et al.
Published: (2025)

Speeding-up Graph Algorithms via Clique Partitioning
by: Chavan, Akshar, et al.
Published: (2025)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
by: Chuzhoy, Julia, et al.
Published: (2025)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
by: Roditty, Liam, et al.
Published: (2026)

Almost-Optimal Approximation Algorithms for Global Minimum Cut in Directed Graphs
by: Mosenzon, Ron
Published: (2025)

Sorting and Ranking of Self-Delimiting Numbers with Applications to Outerplanar Graph Isomorphism
by: Kammer, Frank, et al.
Published: (2020)

Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
by: Hommelsheim, Felix, et al.
Published: (2025)

Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
by: Kaudan, Chirag, et al.
Published: (2026)

Approximating the Average-Case Graph Search Problem with Non-Uniform Costs
by: Szyfelbein, Michał
Published: (2025)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
by: DeHaan, Ian, et al.
Published: (2024)

Finding All Bounded-Length Simple Cycles in a Directed Graph -- Revisited
by: Bauernöppel, Frank, et al.
Published: (2025)

Balanced Substructures in Bicolored Graphs
by: Ardra, P. S., et al.
Published: (2024)

Exploiting Low Scanwidth to Resolve Soft Polytomies
by: Bruchhold, Sebastian, et al.
Published: (2025)

Online $b$-Matching with Stochastic Rewards
by: Albers, Susanne, et al.
Published: (2024)

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
by: Ibrahimpur, Sharat, et al.
Published: (2025)

Structure and Independence in Hyperbolic Uniform Disk Graphs
by: Bläsius, Thomas, et al.
Published: (2024)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
by: MacRury, Calum, et al.
Published: (2022)

Splittable Spanning Trees and Balanced Forests in Dense Random Graphs
by: Gillman, David, et al.
Published: (2025)

Single-Source Shortest Paths and Almost Exact Diameter in Pseudodisk Graphs
by: de Berg, Mark, et al.
Published: (2026)

Decentralized Distributed Graph Coloring: Cluster Graphs
by: Flin, Maxime, et al.
Published: (2024)

The Voronoi Diagram of Weakly Smooth Planar Point Sets in $O(\log n)$ Deterministic Rounds on the Congested Clique
by: Jansson, Jesper, et al.
Published: (2024)

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the $Ω(\log n)$ Lightness Barrier
by: Le, Hung, et al.
Published: (2023)

A Polynomial Kernel for Vertex Deletion to the Scattered Class of Proper Interval Graph and Trees
by: Jacob, Ashwin, et al.
Published: (2026)

Fast FPT Algorithms for Grundy Number on Dense Graphs
by: Nezhad, Sina Ghasemi, et al.
Published: (2024)

Graphs with no long claws: An improved bound for the analog of the Gyárfás' path argument
by: Bourneuf, Romain, et al.
Published: (2025)

Structural Parameterization of Steiner Tree Packing
by: Hastrich, Niko, et al.
Published: (2025)

Fast and Simple Sorting Using Partial Information
by: Haeupler, Bernhard, et al.
Published: (2024)

JFR: An Efficient Jump Frontier Relaxation Strategy for Bellman-Ford
by: Wang, Xin, et al.
Published: (2025)

Customizable Contraction Hierarchies -- A Survey
by: Bläsius, Thomas, et al.
Published: (2025)