REOPTIMIZATION UNDER VERTEX INSERTION: MAX Pk-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH

DOI10.1142/S1793830913600045zbMath1271.05063OpenAlexW1984149217MaRDI QIDQ2846477

Jérôme Monnot, Nicolas Boria, Vangelis Th. Paschos

Publication date: 5 September 2013

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830913600045

zbMATH Keywords

optimal solutionbin packing

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

Unnamed Item ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

Cites Work

• Unnamed Item
• Reoptimizing the 0-1 knapsack problem
• Reoptimization of the shortest common superstring problem
• Graph minors. XX: Wagner's conjecture
• Reoptimization of Steiner trees: changing the terminal set
• Fast reoptimization for the minimum spanning tree problem
• Reoptimization of the metric deadline TSP
• On finite affine line transitive planes
• New Reoptimization Techniques applied to Steiner Tree Problem
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Reoptimizing the traveling salesman problem
• Scheduling with forbidden sets

This page was built for publication: REOPTIMIZATION UNDER VERTEX INSERTION: MAX P_k-FREE SUBGRAPH AND MAX PLANAR SUBGRAPH