Cover Image

The Algorithmic Phase Transition of Random Graph Alignment Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Du, Hang, Gong, Shuyang, Huang, Rundong
Format:	Preprint
Published:	2023
Subjects:	Probability Data Structures and Algorithms 60C05, 68R10, 05C80
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations
by: Gurski, Frank, et al.
Published: (2024)

Set-valued recursions arising from vantage-point trees
by: Dong, Congzao, et al.
Published: (2023)

Reconfiguration of Independent Transversals
by: Buys, Pjotr, et al.
Published: (2024)

Structural results for the Tree Builder Random Walk
by: Engländer, Janos, et al.
Published: (2023)

On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction
by: Onofri, Elia
Published: (2024)

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
by: Wang, Chen, et al.
Published: (2023)

Optimal Adjacency Labels for Subgraphs of Cartesian Products
by: Esperet, Louis, et al.
Published: (2022)

BFS versus DFS for random targets in ordered trees
by: Dimitrov, Stoyan, et al.
Published: (2024)

Degree Realization by Bipartite Cactus Graphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

Stochastic optimization on matrices and a graphon McKean-Vlasov limit
by: Harchaoui, Zaid, et al.
Published: (2022)

Computing the probability of intersection
by: Barvinok, Alexander
Published: (2025)

Tight bounds on adjacency labels for monotone graph classes
by: Bonnet, Édouard, et al.
Published: (2023)

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
by: Bonnet, Édouard, et al.
Published: (2023)

Temporal Exploration of Random Spanning Tree Models
by: Baguley, Samuel, et al.
Published: (2025)

An Algorithm to Recover Shredded Random Matrices
by: Atamanchuk, Caelan, et al.
Published: (2023)

Two-Point Concentration of the Domination Number of Random Graphs
by: Bohman, Tom, et al.
Published: (2024)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

Obstructions to Erdős-Pósa Dualities for Minors
by: Paul, Christophe, et al.
Published: (2024)

Optimal root recovery for uniform attachment trees and $d$-regular growing trees
by: Addario-Berry, Louigi, et al.
Published: (2024)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

A bijection for the evolution of $B$-trees
by: Burghart, Fabian, et al.
Published: (2024)

Random $2$-SAT: The set of atoms of the limiting empirical marginal distribution
by: Müller, Noela, et al.
Published: (2024)

Fundamentals of Partial Rejection Sampling
by: Jerrum, Mark
Published: (2021)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
by: Liao, I-Cheng, et al.
Published: (2023)

Genealogies of records of stochastic processes with stationary increments as unimodular trees
by: Baccelli, François, et al.
Published: (2024)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

Patricia's Bad Distributions
by: Addario-Berry, Louigi, et al.
Published: (2024)

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
by: Chiu, Yung-Chung, et al.
Published: (2021)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

A phase transition in block-weighted random maps
by: Fleurat, William, et al.
Published: (2023)

Unified study of the phase transition for block-weighted random planar maps
by: Salvy, Zéphyr
Published: (2024)

Colorful Minors
by: Protopapas, Evangelos, et al.
Published: (2025)

Cops and Robbers on Multi-Layer Graphs
by: Enright, Jessica, et al.
Published: (2023)

Branch-width of represented matroids in matrix multiplication time
by: Choi, Mujin, et al.
Published: (2026)

Correcting the Foundational Analysis of Karp--Vazirani--Vazirani (STOC 1990): A Rigorous Revision of the $1-1/e$ Upper Bound
by: Xu, Pan
Published: (2025)

Random friend trees
by: Berry, Louigi Addario, et al.
Published: (2024)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
by: Morelle, Laure, et al.
Published: (2025)