Finding the maximum subgraph of prescribed strength

DOI10.1002/NET.70019MaRDI QIDQ6848854zbMATH OpenFDO

Authors Pavlo A. Krokhmal

Publication date 5 March 2026

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/NET.70019

zbMATH Keywords

graph connectivitymaximum subgraph problemspanning tree packing problemstrength of a graph

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Cites work

• A fast algorithm for the maximum clique problem
• A faster algorithm for computing the strength of a network
• A linear programming approach to increasing the weight of all minimum spanning trees
• A model for optimal reinforcement of error- and attack-resilient clusters in networks under uncertainty
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• An improved branch and bound algorithm for the maximum clique problem
• Beyond the flow decomposition barrier
• Clique relaxations in social network analysis: the maximum k-plex problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing the Strength of a Graph
• Computing weighted strength and applications to partitioning
• Detecting resilient structures in stochastic networks: A two‐stage stochastic optimization approach
• Edge-Disjoint Spanning Trees of Finite Graphs
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Finding maximum subgraphs with relatively large vertex connectivity
• scientific article; zbMATH DE number 437577 (Why is no real title available?)
• scientific article; zbMATH DE number 2040957 (Why is no real title available?)
• Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights
• Improvements to MCS algorithm for the maximum clique problem
• Node-and edge-deletion NP-complete problems
• On Cayley's formula for counting forests
• On risk-averse maximum weighted subgraph problems
• On the maximum quasi-clique problem
• On the Problem of Decomposing a Graph into n Connected Factors
• Optimal attack and reinforcement of a network
• Risk‐averse optimization and resilient network flows
• Separating from the dominant of the spanning tree polytope
• Strength of a graph and packing of trees and branchings

This page was built for publication: Finding the maximum subgraph of prescribed strength

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6848854)