Scalable algorithms for 2-packing sets on arbitrary graphs

DOI10.7155/JGAA.V29I1.3064MaRDI QIDQ7232115zbMATH OpenFDO

Authors Jannick Borowitz, Ernestine Großmann, Christian Schulz, Dominik Schweisgut

Publication date 22 April 2026

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.7155/JGAA.V29I1.3064

zbMATH Keywords

2-packing setalgorithm engineeringdata reduction

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
• A genetic algorithm for the maximum 2-packing set problem
• A hybrid iterated local search heuristic for the maximum weight independent set problem
• A metaheuristic algorithm for large maximum weight independent set problems
• A self-stabilizing algorithm for a maximal 2-packing in a cactus graph under any scheduler
• A self-stabilizing algorithm to maximal 2-packing with improved complexity
• Algorithm to find a maximum 2-packing set in a cactus
• Approximation algorithms for NP-complete problems on planar graphs
• Benchmarking optimization software with performance profiles.
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Data reduction and exact algorithms for clique cover
• Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
• Effective data reduction for the vertex clique cover problem
• Efficient transformation of distance-2 self-stabilizing algorithms
• Exactly solving the maximum weight independent set problem on large real-world graphs
• Fast local search for the maximum independent set problem
• Finding near-optimal independent sets at scale
• Finding near-optimal weight independent sets at scale
• scientific article; zbMATH DE number 1223713 (Why is no real title available?)
• scientific article; zbMATH DE number 2061538 (Why is no real title available?)
• scientific article; zbMATH DE number 2114409 (Why is no real title available?)
• On the power of simple reductions for the maximum independent set problem
• Parameterized algorithms
• Simple recognition of Halin graphs and their generalizations
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• The packing number of the double vertex graph of the path graph

This page was built for publication: Scalable algorithms for 2-packing sets on arbitrary graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7232115)