Finding optimal subgraphs by local search

DOI10.1016/S0304-3975(96)00135-1zbMath0903.68051OpenAlexW1975037714MaRDI QIDQ1392027

Shinichi Shimozono

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

zbMATH Keywords

local search problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

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