Computing weighted strength and applications to partitioning

DOI10.1137/15M102914XMaRDI QIDQ4558887zbMATH OpenWikidataFDO

Authors Jérôme Galtier

Publication date 30 November 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/15M102914X

zbMATH Keywords

approximation algorithmclassificationcommunity detectiondendogramgraphic matroidKruskal algorithmmultiplicative-weights-update methodnested clusteringrankingsmall-worldstrength of a graph

Mathematics Subject Classification ID

Connectivity (05C40) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• scientific article; zbMATH DE number 56092
• Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size
• A faster algorithm for computing the strength of a network
• Graph-Theoretic Concepts in Computer Science
• Optimal attack and reinforcement of a network

Cites work

• A faster algorithm for computing the strength of a network
• Algorithms and data structures for external memory
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Beyond the flow decomposition barrier
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing the Strength of a Graph
• Decomposition of Finite Graphs Into Forests
• Edge-Disjoint Spanning Trees of Finite Graphs
• Fast approximation for computing the fractional arboricity and extraction of communities of a graph
• Fast approximation of matroid packing and covering
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 437577 (Why is no real title available?)
• scientific article; zbMATH DE number 5485527 (Why is no real title available?)
• scientific article; zbMATH DE number 3580570 (Why is no real title available?)
• scientific article; zbMATH DE number 910863 (Why is no real title available?)
• scientific article; zbMATH DE number 910872 (Why is no real title available?)
• Introduction to algorithms.
• Matrices and matroids for systems analysis
• Max flows in O(nm) time, or better
• Minimum cuts in near-linear time
• On the Problem of Decomposing a Graph into n Connected Factors
• Optimal attack and reinforcement of a network
• Packing algorithms for arborescences (and spanning trees) in capacitated graphs
• Separating from the dominant of the spanning tree polytope
• Strength of a graph and packing of trees and branchings

Cited in

(6)

• A faster algorithm for computing the strength of a network
• Fast approximation of matroid packing and covering
• Weighted skeletons and fixed-share decomposition
• scientific article; zbMATH DE number 4195959 (Why is no real title available?)
• Finding the maximum subgraph of prescribed strength
• Partitioning a weighted partial order

This page was built for publication: Computing weighted strength and applications to partitioning

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