Advances in Graph Optimization and Temporal Graphs

The field of graph optimization and temporal graphs is witnessing significant developments, with a focus on improving approximation algorithms and exploring new problem formulations. Researchers are making progress in solving complex problems, such as minimum norm optimization, subgraph isomorphism, and temporal graph realization, using innovative techniques like stigmergic swarming agents and ensemble metaheuristics. Noteworthy papers in this area include: New Results on a General Class of Minimum Norm Optimization Problems, which proposes a general formulation for norm minimization problems and achieves constant factor approximation algorithms for several covering problems. O(p log d) Subgraph Isomorphism using Stigmergic Swarming Agents, which outlines a linearithmic algorithm for subgraph isomorphism using ant colony optimization. Temporal Graph Realization With Bounded Stretch, which introduces a natural optimality criterion for temporal graph realization and provides approximation and NP-hardness results. Prize-Collecting Forest with Submodular Penalties: Improved Approximation, which achieves a 2-approximation algorithm for the prize-collecting forest problem with submodular penalties. Linear Time Subsequence and Supersequence Regex Matching, which shows that regex matching for subsequences and supersequences can be solved in linear time. Approximating Optimal Labelings for Temporal Connectivity, which extends our knowledge on the complexity and approximability of the minimum aged labeling problem. A general framework for finding diverse solutions via network flow and its applications, which presents a general framework for efficiently computing diverse solutions to combinatorial optimization problems. Realization of Temporally Connected Graphs Based on Degree Sequences, which characterizes the feasible cases and provides a recognition algorithm for realizing temporally connected graphs based on degree sequences.

Sources

New Results on a General Class of Minimum Norm Optimization Problems

$O(p \log d)$ Subgraph Isomorphism using Stigmergic Swarming Agents

Temporal Graph Realization With Bounded Stretch

An island-parallel ensemble metaheuristic algorithm for large graph coloring problems

Prize-Collecting Forest with Submodular Penalties: Improved Approximation

Linear Time Subsequence and Supersequence Regex Matching

Approximating Optimal Labelings for Temporal Connectivity

A general framework for finding diverse solutions via network flow and its applications

Realization of Temporally Connected Graphs Based on Degree Sequences

Built with on top of