A polynomial characterization of some graph partitioning problems

DOI10.1016/0020-0190(88)90144-5MaRDI QIDQ1108810zbMATH OpenOpenAlexFDO

Authors Claudio Arbib

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90144-5

zbMATH Keywords

graph partitioningpolynomial algorithmline-graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 4112413
• Generalized partitions of graphs
• The partition problem
• scientific article; zbMATH DE number 3970117
• Restrictions of graph partition problems. I

Cites work

• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3770975 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3286813 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• An Efficient Heuristic Procedure for Partitioning Graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• On the cut polytope
• Some simplified NP-complete graph problems
• The max-cut problem on graphs not contractible to \(K_ 5\)

Cited in

(14)

• The equipartition polytope. I: Formulations, dimension and basic facets
• On uniform \(k\)-partition problems
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• \textsc{max-cut} and containment relations in graphs
• Some new classes of facets for the equicut polytope
• SIMPLE MAX-CUT for unit interval graphs and graphs with few \(P4\)s
• Max-Cut and containment relations in graphs
• Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
• A solution to Gutman's problem on the characteristic polynomial of a bipartite graph
• Maximum cut on line and total graphs
• scientific article; zbMATH DE number 4112413 (Why is no real title available?)
• Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps
• A P-complete graph partition problem
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: A polynomial characterization of some graph partitioning problems

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