A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound

DOI10.1016/0012-365X(86)90192-5zbMath0585.05032OpenAlexW1996672997MaRDI QIDQ1071037

Daniel Turzík, Svatopluk Poljak

Publication date: 1986

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(86)90192-5

zbMATH Keywords

graphsspanning subgraphconstructionlambda-extendible graph propertylarge acyclic graphslarge balanced graphslarge bipartite

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (17)

Unnamed Item ⋮ A survey on the linear ordering problem for weighted or unweighted tournaments ⋮ Linear-Time Approximation Algorithms for the Max Cut Problem ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ A survey of graph laplacians ⋮ Lower Bounds for Maximum Weighted Cut ⋮ Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound ⋮ Voting Procedures, Complexity of ⋮ On existence theorems ⋮ Max-cut in circulant graphs ⋮ The cut cone. III: On the role of triangle facets ⋮ An updated survey on the linear ordering problem for weighted or unweighted tournaments ⋮ The cut cone. III: On the role of triangle facets ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ Checking robust nonsingularity is NP-hard ⋮ Acyclic Digraphs ⋮ Judicious partitions of graphs

Cites Work

• Weakly bipartite graphs and the max-cut problem
• Some simplified NP-complete graph problems
• Facets of the Bipartite Subgraph Polytope
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• P-Complete Approximation Problems
• An algorithm for the blocks and cutnodes of a graph
• Optimal ranking of tournaments
• Depth-First Search and Linear Graph Algorithms
• Some Extremal Properties of Bipartite Subgraphs
• Unnamed Item

This page was built for publication: A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound