Efficient Maximum s-Bundle Search via Local Vertex Connectivity
Summary: SymBD, a branch-and-bound solver for the maximum s-bundle problem (cohesive subgraph resilient to vertex deletions) using local-vertex-connectivity based orderings. Achieves O*(λ_s^n) with λ_s<2; includes heuristic initial solution, divide-and-conquer, and parallelization, with up to five orders of magnitude speedup on 664 graphs. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Yang Liu (Harbin Engineering University)
- 2. Hejiao Huang (Harbin Engineering University)
- 3. Kaiqiang Yu (Nanyang Technological University)
- 4. Shengxin Liu (Harbin Engineering University)
- 5. Cheng Long (Nanyang Technological University)
BibTeX Citation
@inproceedings{liu_sigmod25,
title = {{Efficient Maximum s-Bundle Search via Local Vertex Connectivity}},
author = {Liu, Yang and Huang, Hejiao and Yu, Kaiqiang and Liu, Shengxin and Long, Cheng},
series = {{SIGMOD} '25},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3709687},
url = {https://dl.acm.org/doi/10.1145/3709687},
year = {2025}
}Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,913 | Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space | 2026 | SIGMOD | 5.2361195e-05 |
| 10,395 | Efficient Querying of Maximum Connectivity-Based Quasi-Cliques in Large Graphs | 2027 | SIGMOD | 4.9605343e-05 |
| 10,639 | Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements | 2026 | SIGMOD | 4.9605343e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 19 of 19 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 4,567 | Efficiently Computing k-Edge Connected Components via Graph Decomposition | 2013 | SIGMOD |
| 2 | 3,591 | Efficient Maximum k-Defective Clique Computation with Improved Time Complexity | 2023 | SIGMOD |
| 3 | 11,573 | Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee | 2024 | SIGMOD |
| 4 | 4,155 | Maximal Defective Clique Enumeration | 2023 | SIGMOD |
| 5 | 4,606 | Maximum k-Biplex Search on Bipartite Graphs: A Symmetric-BK Branching Approach | 2023 | SIGMOD |
| 6 | 8,913 | Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space | 2026 | SIGMOD |
| 7 | 3,431 | Efficient Size-Bounded Community Search over Large Networks | 2021 | VLDB |
| 8 | 10,639 | Efficient Size-Bounded Community Search, Revisited: Frameworks for Practical Improvements | 2026 | SIGMOD |
| 9 | 5,569 | Theoretically and Practically Efficient Maximum Defective Clique Search | 2024 | SIGMOD |
| 10 | 3,597 | Efficient k-Clique Listing: An Edge-Oriented Branching Strategy | 2024 | SIGMOD |