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 partitioningline-graphspolynomial algorithm

Mathematics Subject Classification ID

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

Review text

The uniform partition (UP) and the simple max partition (SMP) problems are NP-complete graph partitioning problems, and polynomial-time algorithms are known for few classes of graphs only. In the present paper, the class of line-graphs is considered and a polynomial algorithm is proposed to solve both problems in this class. When the instance space is extended to digraphs, a characterization is possible which leads to similar results.

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

• 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
• 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?)
• On the cut polytope
• Some simplified NP-complete graph problems
• The max-cut problem on graphs not contractible to \(K_ 5\)

Cited in

(14)

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

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)