On minimum vertex bisection of random \(d\)-regular graphs
From MaRDI portal
Publication:6564623
DOI10.1016/j.jcss.2024.103550MaRDI QIDQ6564623
Oriol Serra, Maria J. Serna, Öznur Yaşar Diner, Josep Diaz
Publication date: 1 July 2024
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The cook-book approach to the differential equation method
- On the parameterized complexity of computing balanced partitions in graphs
- On the bipartition of graphs
- The isoperimetric number of random regular graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Some simplified NP-complete graph problems
- The asymptotic number of labeled graphs with given degree sequences
- The diameter of random regular graphs
- Bounds on the max and min bisection of random cubic and random 4-regular graphs
- Bounds on the bisection width for random \(d\)-regular graphs
- Minimum bisection is NP-hard on unit disk graphs
- An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
- Vertex Bisection is Hard, too
- An Efficient Heuristic Procedure for Partitioning Graphs
- On the Edge-Expansion of Graphs
- The bisection width of cubic graphs
- Uniform Generation of Random Regular Graphs
- Lower Bounds for the Isoperimetric Numbers of Random Regular Graphs
- Exact Combinatorial Branch-and-Bound for Graph Bisection
- Factors of IID on Trees
- Optimal numberings and isoperimetric problems on graphs
- Solutions of ordinary differential equations as limits of pure jump markov processes
- Optimal Assignments of Numbers to Vertices
- LINEAR LAYOUT OF GENERALIZED HYPERCUBES
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
This page was built for publication: On minimum vertex bisection of random \(d\)-regular graphs
