A faster algorithm for computing the principal sequence of partitions of a graph
DOI10.1007/S00453-008-9177-ZzbMATH Open1187.05071OpenAlexW1980424220MaRDI QIDQ848839FDOQ848839
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
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
network strengthminimum cut/maximum flowparametric algorithmnetwork attackprincipal sequence of partitions
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)
Cites Work
- A data structure for dynamic trees
- Self-adjusting binary search trees
- A new approach to the maximum-flow problem
- A Separator Theorem for Planar Graphs
- A Fast Parametric Maximum Flow Algorithm and Applications
- Title not available (Why is that?)
- Submodular functions and optimization
- Submodular functions and electrical networks
- NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
- Mathematical Techniques for Efficient Record Segmentation in Large Shared Databases
- Optimal attack and reinforcement of a network
- Optimal cooperation and submodularity for computing Potts partition functions with a large number of states
- A faster algorithm for computing the strength of a network
- Fast Algorithms for Parametric Scheduling Come From Extensions to Parametric Maximum Flow
- Separating from the dominant of the spanning tree polytope
- Separation of partition inequalities
- The principal lattice of partitions of a submodular function
- Fast on-line/off-line algorithms for optimal reinforcement of a network and its connections with principal partition
- Computing the Strength of a Graph
- Title not available (Why is that?)
- Algorithms for Graphic Polymatroids and Parametrics-Sets
Cited In (5)
- LP Relaxation and Tree Packing for Minimum $k$-Cut
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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)
