Finding optimal subgraphs by local search
From MaRDI portal
Publication:1392027
DOI10.1016/S0304-3975(96)00135-1zbMath0903.68051OpenAlexW1975037714MaRDI QIDQ1392027
Publication date: 23 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00135-1
Cites Work
- Local search, reducibility and approximability of NP-optimization problems
- How easy is local search?
- The node-deletion problem for hereditary properties is NP-complete
- Towards a complexity theory of synchronous parallel computation
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- A note on the approximation of the MAX CLIQUE problem
- Parallel concepts in graph theory
- Simple Local Search Problems that are Hard to Solve
- On Finding and Verifying Locally Optimal Solutions
- A New Parallel Algorithm for the Maximal Independent Set Problem
- The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
- The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
- The approximation of maximum subgraph problems
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This page was built for publication: Finding optimal subgraphs by local search