Reoptimization of maximum weight induced hereditary subgraph problems
DOI10.1016/J.TCS.2012.10.037zbMATH Open1277.68085OpenAlexW2085587857MaRDI QIDQ386899FDOQ386899
Authors: Nicolas Boria, Jérôme Monnot, Vangelis Th. Paschos 
Publication date: 11 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.10.037
Recommendations
- Reoptimization of some maximum weight induced hereditary subgraph problems
- Reoptimization of the maximum weighted \(P_{k }\)-free subgraph problem under vertex insertion
- On-line computation and maximum-weighted hereditary subgraph problems
- Algorithms and Computation
- Reoptimization of Weighted Graph and Covering Problems
- On-line maximum-order induced hereditary subgraph problems
- scientific article; zbMATH DE number 2079869
- Algorithms for the maximum weight connected \(k\)-induced subgraph problem
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
- On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Graph minors. XX: Wagner's conjecture
- A data structure for dynamic trees
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Approximating Maximum Clique by Removing Subgraphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Title not available (Why is that?)
- Reoptimization of the metric deadline TSP
- Knowing all optimal solutions does not help for TSP reoptimization
- Title not available (Why is that?)
- On the Hardness of Reoptimization with Multiple Given Solutions
- On the Hardness of Reoptimization
- The approximation of maximum subgraph problems
- Simple and fast reoptimizations for the Steiner tree problem
- Reoptimizing the traveling salesman problem
- Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
- Reoptimizing the 0-1 knapsack problem
- Approximating maximum independent sets by excluding subgraphs
- On finite affine line transitive planes
- New reoptimization techniques applied to Steiner tree problem
- Reoptimization of Steiner Trees
- The Steiner tree reoptimization problem with sharpened triangle inequality (extended abstract)
- Reoptimization of Weighted Graph and Covering Problems
- Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights
- Maintaining minimum spanning trees in dynamic graphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Scheduling with forbidden sets
- Reoptimization of the shortest common superstring problem
- Reoptimization of Steiner trees: changing the terminal set
- Fast reoptimization for the minimum spanning tree problem
Cited In (12)
- A survey on combinatorial optimization in dynamic environments
- Reoptimization of the maximum weighted \(P_{k }\)-free subgraph problem under vertex insertion
- Reoptimization of some maximum weight induced hereditary subgraph problems
- New algorithms for Steiner tree reoptimization
- New algorithms for Steiner tree reoptimization
- Reoptimization under vertex insertion: max \(P_{k}\)-free subgraph and max planar subgraph
- On Lagrangian relaxation for constrained maximization and reoptimization problems
- Hardness of reoptimization of the problem of calculating the chromatic number of a graph with a given set of optimal solutions
- Reoptimization of Weighted Graph and Covering Problems
- A note on the traveling salesman reoptimization problem under vertex insertion
- Robust reoptimization of Steiner trees
- Reoptimization of minimum latency problem revisited: don't panic when asked to revisit the route after local modifications
This page was built for publication: Reoptimization of maximum weight induced hereditary subgraph problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q386899)
