scientific article; zbMATH DE number 3983202

MaRDI QIDQ3748301zbMATH OpenFDO

Authors Gy. Turán

Publication date 1986

zbMATH Keywords

approximation ratioedge-partitiongreedy algorithmpattern graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On Computational Aspects of Greedy Partitioning of Graphs
• Computational aspects of greedy partitioning of graphs
• On the complexity of some edge-partition problems for graphs
• Analysis of an approximate greedy algorithm for the maximum edge clique partitioning problem
• Algorithms for the Balanced Edge Partitioning Problem
• scientific article; zbMATH DE number 1241383
• Approximation Algorithms for Some Graph Partitioning Problems
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• Approximation algorithms for maximization problems arising in graph partitioning
• Greedy splitting algorithms for approximating multiway partition problems

Cited in

(7)

• Computational aspects of greedy partitioning of graphs
• On generalized greedy splitting algorithms for multiway partition problems
• scientific article; zbMATH DE number 1342136 (Why is no real title available?)
• On Computational Aspects of Greedy Partitioning of Graphs
• Unexpected failure of a greedy choice algorithm proposed by Hoffman
• Partitioning the edge set of a bipartite graph into the minimal number of subgraphs isomorphic to those of a simple 4 order cycle
• Maximizing edge-ratio is NP-complete

This page was built for publication:

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