On the approximability of the minimum rainbow subgraph problem and other related problems

DOI10.1007/S00453-017-0278-4zbMATH Open1380.68451OpenAlexW2572273493MaRDI QIDQ1679237FDOQ1679237

Authors: Sumedh Tirodkar, Sundar Vishwanathan 

Publication date: 9 November 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0278-4

Recommendations

• On the approximability of the minimum rainbow subgraph problem and other related problems
• Improved approximation bounds for the minimum rainbow subgraph problem
• Approximation algorithms for the minimum rainbow subgraph problem
• Algorithmic approaches for the minimum rainbow subgraph problem
• On the minimum rainbow subgraph number of a graph

zbMATH Keywords

approximation algorithmdensest \(k\)-subgraph problemMIN-REP

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• A threshold of ln n for approximating set cover
• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• The dense \(k\)-subgraph problem
• Title not available (Why is that?)
• On restricted colourings of \(K_ n\)
• Title not available (Why is that?)
• Approximation Algorithms and Hardness for Domination with Propagation
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
• Title not available (Why is that?)
• Rainbow subgraphs in properly edge‐colored graphs
• Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
• Improved approximation bounds for the minimum rainbow subgraph problem
• The parameterized complexity of the rainbow subgraph problem
• Approximation algorithms for the minimum rainbow subgraph problem
• Improved approximation algorithms for label cover problems
• On the hardness of approximating spanners
• Approximating the rainbow -- better lower and upper bounds

Cited In (6)

• On the approximability of the minimum rainbow subgraph problem and other related problems
• Improved approximation bounds for the minimum rainbow subgraph problem
• On the minimum rainbow subgraph number of a graph
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Revisiting a randomized algorithm for the minimum rainbow subgraph problem

This page was built for publication: On the approximability of the minimum rainbow subgraph problem and other related problems

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