Approximations of Weighted Independent Set and Hereditary Subset Problems

DOI10.7155/JGAA.00020MaRDI QIDQ4504997zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Magnús M. Halldórsson

Publication date 19 September 2000

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

Full work available at URL https://eudml.org/doc/233681

zbMATH Keywords

bounded-degree graphshereditary subgraph and subset probleminductive graphsmaximum independent set problemsparse graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1405687
• Improved approximations for weighted and unweighted graph problems
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Graph-Theoretic Concepts in Computer Science
• A note on the approximation of a minimum-weight maximal independent set

Cited in

(40)

• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• Approximation algorithms for the weighted independent set problem in sparse graphs
• Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
• On the hardness of approximating max-satisfy
• Local approximations for maximum partial subgraph problem.
• Approximating weighted neighborhood independent sets
• The graph segmentation problem
• On the differential approximation of MIN SET COVER
• Polynomial approximation algorithms with performance guarantees: an introduction-by-example
• On the approximability of clique and related maximization problems
• Speeding-up structured probabilistic inference using pattern mining
• Inapproximability and approximability of maximal tree routing and coloring
• Truthful approximation mechanisms for restricted combinatorial auctions
• Improved approximations for weighted and unweighted graph problems
• On Lagrangian relaxation for constrained maximization and reoptimization problems
• Pricing on paths: a PTAS for the highway problem
• On the maximum uniquely restricted matching for bipartite graphs
• Maximum weighted independent sets with a budget
• An effective discrete dynamic convexized method for solving the winner determination problem
• On-line models and algorithms for max independent set
• Combinatorial auctions with conflict-based externalities
• Approximating Independent Set and Coloring in Random Uniform Hypergraphs
• On Lagrangian Relaxation and Subset Selection Problems
• On vertex independence number of uniform hypergraphs
• On the Lovász Theta Function for Independent Sets in Sparse Graphs
• On constant time approximation of parameters of bounded degree graphs
• scientific article; zbMATH DE number 1405687 (Why is no real title available?)
• Bilu-Linial stability, certified algorithms and the independent set problem
• Inductive graph invariants and approximation algorithms
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Interdiction Games and Monotonicity, with Application to Knapsack Problems
• The power of oblivious wireless power
• Equilibria of greedy combinatorial auctions
• Graph-Theoretic Concepts in Computer Science
• Comparing the hardness of online minimization and maximization problems with predictions
• Linearly ordered colourings of hypergraphs
• Improved linearly ordered colorings of hypergraphs via SDP rounding
• Independent sets in semi-random hypergraphs
• Longest common subsequence problem for unoriented and cyclic strings
• Approximating maximum satisfiable subsystems of linear equations of bounded width

This page was built for publication: Approximations of Weighted Independent Set and Hereditary Subset Problems

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