A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- 31 January 1986
- journal article
- research article
- Published by Elsevier in Discrete Mathematics
- Vol. 58 (1) , 99-104
- https://doi.org/10.1016/0012-365x(86)90192-5
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- Facets of the Bipartite Subgraph PolytopeMathematics of Operations Research, 1985
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability ProblemCanadian Journal of Mathematics, 1982
- Weakly bipartite graphs and the Max-cut problemOperations Research Letters, 1981
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- Some Extremal Properties of Bipartite SubgraphsCanadian Journal of Mathematics, 1973
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- Theoretical Improvements in Algorithmic Efficiency for Network Flow ProblemsJournal of the ACM, 1972
- An algorithm for the blocks and cutnodes of a graphCommunications of the ACM, 1971
- Optimal ranking of tournamentsNetworks, 1971