Solving minimum K-cardinality cut problems in planar graphs

DOI10.1002/NET.20129MaRDI QIDQ3418207zbMATH OpenOpenAlexFDO

Authors Maurizio Bruglieri, Francesco Maffioli, Marco Trubian

Publication date 2 February 2007

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20129

zbMATH Keywords

cut problemsexact perfect matchingLagrangian relaxationminimum \(k\)-cardinality cutplanar graphssemidefinite programming

Mathematics Subject Classification ID

Connectivity (05C40) Programming involving graphs or networks (90C35)

Recommendations

• Cardinality constrained minimum cut problems: complexity and algorithms.
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• The planar multiterminal cut problem

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Systems of distinct representatives and linear algebra

Cited in

(6)

• Cardinality constrained minimum cut problems: complexity and algorithms.
• Efficient algorithms for \(k\)-terminal cuts on planar graphs
• Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time
• Partitioning planar graphs: a fast combinatorial approach for max-cut
• An optimal algorithm for the minimum edge cardinality cut surface problem
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)

Describes a project that uses

Uses Software

• CSDP

This page was built for publication: Solving minimum K-cardinality cut problems in planar graphs

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