Efficient polynomial-time algorithms for special graph partitioning problems

zbMATH Open1297.05003MaRDI QIDQ2877347FDOQ2877347

Authors: G. Pardella 

Publication date: 22 August 2014

Recommendations

• Partitioning planar graphs: a fast combinatorial approach for max-cut
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Optimization via enumeration: A new algorithm for the max cut problem
• A linear time algorithm for graph partition problems
• Optimal cuts in graphs and statistical mechanics

zbMATH Keywords

Ising spin glassesmaximum weight matching problem on planar graphspolynomial-time solvable optimization problems

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (4)

• Optimal cuts in graphs and statistical mechanics
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• Combinatorial optimization of special graphs for nodal ordering and graph partitioning
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

This page was built for publication: Efficient polynomial-time algorithms for special graph partitioning problems

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