Maximum weight t-sparse set problem on vector-weighted graphs

DOI10.1051/RO/2023145MaRDI QIDQ6140983FDOQ6140983

Authors Yuquan Lin, Wensong Lin 

Publication date 22 January 2024

Published in RAIRO - Operations Research (Search for Journal in Brave)

zbMATH Keywords

treewidthmaximum weightvector weightsouterplane graphs\(t\)-sparse sets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Extremal problems in graph theory (05C35) Vertex degrees (05C07) Signed and weighted graphs (05C22)

Recommendations

• Approximation algorithms for the weighted independent set problem in sparse graphs
• Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
• Algorithms for finding an independent \(\{K_1,K_2\}\)-packing of maximum weight in a graph
• Efficient computation of tolerances in the weighted independent set problem for some classes of graphs
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs

Cites work

• scientific article; zbMATH DE number 1354124 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A generalization of Nemhauser and Trotter's local optimization theorem
• A graph‐theoretic generalization of the clique concept
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• An improved approximation for maximum \(k\)-dependent set on bipartite graphs
• An optimal time algorithm for finding a maximum weight independent set in a tree
• Approximation algorithms for finding and partitioning unit-disk graphs into co-\(k\)-plexes
• Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
• Clique relaxations in social network analysis: the maximum \(k\)-plex problem
• Co-2-plex vertex partitions
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Every property of hyperfinite graphs is testable
• Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems
• Improper coloring of unit disk graphs
• Independent sets of maximum weight in apple-free graphs
• Maximal and maximum dissociation sets in general and triangle-free graphs
• Node-Deletion Problems on Bipartite Graphs
• On bounded-degree vertex deletion parameterized by treewidth
• On maximal independent sets of vertices in claw-free graphs
• Parameterized algorithms
• Some defective parameters in graphs
• The \(t\)-stability number of a random graph
• The maximum number of maximum dissociation sets in trees

This page was built for publication: Maximum weight t-sparse set problem on vector-weighted graphs

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