Approximations of Weighted Independent Set and Hereditary Subset Problems

DOI10.7155/JGAA.00020zbMath0952.05069OpenAlexW2017052164WikidataQ56210417 ScholiaQ56210417MaRDI QIDQ4504997

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

maximum independent set problemsparse graphsbounded-degree graphsinductive graphshereditary subgraph and subset problem

Mathematics Subject Classification ID

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

Related Items (34)

On the approximability of clique and related maximization problems ⋮ Independent sets in semi-random hypergraphs ⋮ An effective discrete dynamic convexized method for solving the winner determination problem ⋮ Combinatorial Auctions with Conflict-Based Externalities ⋮ Longest common subsequence problem for unoriented and cyclic strings ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ On Lagrangian relaxation for constrained maximization and reoptimization problems ⋮ On vertex independence number of uniform hypergraphs ⋮ Inductive graph invariants and approximation algorithms ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Maximum Weighted Independent Sets with a Budget ⋮ Local approximations for maximum partial subgraph problem. ⋮ Interdiction Games and Monotonicity, with Application to Knapsack Problems ⋮ The graph segmentation problem ⋮ Recoverable Values for Independent Sets ⋮ Approximating maximum satisfiable subsystems of linear equations of bounded width ⋮ Equilibria of Greedy Combinatorial Auctions ⋮ Unnamed Item ⋮ On the differential approximation of MIN SET COVER ⋮ Polynomial approximation algorithms with performance guarantees: an introduction-by-example ⋮ On Constant Time Approximation of Parameters of Bounded Degree Graphs ⋮ Inapproximability and approximability of maximal tree routing and coloring ⋮ Approximating Independent Set and Coloring in Random Uniform Hypergraphs ⋮ On Lagrangian Relaxation and Subset Selection Problems ⋮ Pricing on Paths: A PTAS for the Highway Problem ⋮ Truthful approximation mechanisms for restricted combinatorial auctions ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Approximation algorithms for the weighted independent set problem in sparse graphs ⋮ On the Maximum Uniquely Restricted Matching for Bipartite Graphs ⋮ On-line models and algorithms for max independent set ⋮ Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth ⋮ On the hardness of approximating max-satisfy ⋮ The Power of Oblivious Wireless Power ⋮ Speeding-up structured probabilistic inference using pattern mining

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