Cover Image

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zhou, Yi, Luo, Chunyu, Wang, Zhengren, Fu, Zhang-Hua
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem
by: Luo, Chunyu, et al.
Published: (2024)

Efficient Branch-and-Bound for Submodular Function Maximization under Knapsack Constraint
by: Hao, Yimin, et al.
Published: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
by: Haeupler, Bernhard, et al.
Published: (2025)

Fast Maximum Common Subgraph Search: A Redundancy-Reduced Backtracking Approach
by: Yu, Kaiqiang, et al.
Published: (2025)

Dense Subgraph Discovery Meets Strong Triadic Closure
by: Arachchi, Chamalee Wickrama, et al.
Published: (2025)

Accelerating Maximum Common Subgraph Computation by Exploiting Symmetries
by: Kothalawala, Buddhi, et al.
Published: (2026)

Forbidden Subgraph Problems with Predictions
by: Böckenhauer, Hans-Joachim, et al.
Published: (2025)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
by: Xue, Jinghui, et al.
Published: (2024)

Two New Upper Bounds for the Maximum k-plex Problem
by: Zheng, Jiongzhi, et al.
Published: (2023)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
by: Haeupler, Bernhard, et al.
Published: (2026)

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
by: Gao, Xuan-Zhao, et al.
Published: (2024)

Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited
by: Hanaka, Tesshu, et al.
Published: (2025)

Scalable $k$-clique Densest Subgraph Search
by: Ye, Xiaowei, et al.
Published: (2024)

Almost Tight Bounds for Differentially Private Densest Subgraph
by: Dinitz, Michael, et al.
Published: (2023)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
by: Sun, Ming, et al.
Published: (2022)

Counting Cohesive Subgraphs with Hereditary Properties
by: Li, Rong-Hua, et al.
Published: (2024)

Near-Optimal Directed Low-Diameter Decompositions
by: Bringmann, Karl, et al.
Published: (2025)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
by: Çivril, Ali
Published: (2023)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
by: Chan, Timothy M., et al.
Published: (2025)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
by: Li, Jason, et al.
Published: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
by: Chalermsook, Parinya, et al.
Published: (2021)

Fast and Optimal Incremental Parametric Procedure for the Densest Subgraph Problem: An Experimental Study
by: Hochbaum, Dorit S., et al.
Published: (2025)

Efficient Top-k s-Biplexes Search over Large Bipartite Graphs
by: Xu, Zhenxiang, et al.
Published: (2024)

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
by: Chuzhoy, Julia, et al.
Published: (2026)

Packing Compact Subgraphs with Applications to Districting
by: Chen, Ho-Lin, et al.
Published: (2026)

KD-Club: An Efficient Exact Algorithm with New Coloring-based Upper Bound for the Maximum k-Defective Clique Problem
by: Jin, Mingming, et al.
Published: (2023)

The Complexity Landscape of Dynamic Distributed Subgraph Finding
by: Chang, Yi-Jun, et al.
Published: (2024)

Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems
by: Nguyen, Ta Duy, et al.
Published: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
by: Paul-Pena, Daniel, et al.
Published: (2024)

Low-degree Security of the Planted Random Subgraph Problem
by: Bogdanov, Andrej, et al.
Published: (2024)

A Survey on the Densest Subgraph Problem and Its Variants
by: Lanciano, Tommaso, et al.
Published: (2023)

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
by: Suga, Tatsuhiro, et al.
Published: (2025)

In-depth Analysis of Densest Subgraph Discovery in a Unified Framework
by: Zhou, Yingli, et al.
Published: (2024)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

Finding Order-Preserving Subgraphs
by: Imamura, Haruya, et al.
Published: (2025)

Destroying Densest Subgraphs is Hard
by: Bazgan, Cristina, et al.
Published: (2024)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing
by: Bshouty, Nader H.
Published: (2026)