A faster algorithm for computing the principal sequence of partitions of a graph

DOI10.1007/S00453-008-9177-ZMaRDI QIDQ848839zbMATH OpenOpenAlexFDO

Authors Vladimir Kolmogorov

Publication date 23 February 2010

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-008-9177-z

zbMATH Keywords

network strengthminimum cut/maximum flowparametric algorithmnetwork attackprincipal sequence of partitions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 3970117
• Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
• Fast Approximate Graph Partitioning Algorithms
• Algorithms for graph partitioning problems by means of eigenspace relaxations
• scientific article; zbMATH DE number 4047774

Cites work

• scientific article; zbMATH DE number 1301104 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A Fast Parametric Maximum Flow Algorithm and Applications
• A Separator Theorem for Planar Graphs
• A data structure for dynamic trees
• A faster algorithm for computing the strength of a network
• A new approach to the maximum-flow problem
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Computing the Strength of a Graph
• Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
• Fast on-line/off-line algorithms for optimal reinforcement of a network and its connections with principal partition
• Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
• NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
• Optimal attack and reinforcement of a network
• Optimal cooperation and submodularity for computing Potts  partition functions with a large number of states
• Self-adjusting binary search trees
• Separating from the dominant of the spanning tree polytope
• Separation of partition inequalities
• Submodular functions and electrical networks
• Submodular functions and optimization
• The principal lattice of partitions of a submodular function

Cited in

(5)

• scientific article; zbMATH DE number 4047774 (Why is no real title available?)
• On the structure property of PCR's adjacency graph with a prime order and its application of constructing M-sequences
• Approximating submodular \(k\)-partition via principal partition sequence
• scientific article; zbMATH DE number 2080194 (Why is no real title available?)
• LP relaxation and tree packing for minimum \(k\)-cut

This page was built for publication: A faster algorithm for computing the principal sequence of partitions of a graph

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