On the approximability of the minimum rainbow subgraph problem and other related problems
From MaRDI portal
Publication:1679237
DOI10.1007/s00453-017-0278-4zbMath1380.68451OpenAlexW2572273493MaRDI QIDQ1679237
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
Analysis of algorithms (68W40) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for label cover problems
- Approximation algorithms for the minimum rainbow subgraph problem
- On restricted colourings of \(K_ n\)
- Approximation algorithms for the Label-Cover\(_{\text{MAX}}\) and Red-Blue Set Cover problems
- Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
- Improved approximation bounds for the minimum rainbow subgraph problem
- Detecting high log-densities
- Approximating the Rainbow – Better Lower and Upper Bounds
- The Parameterized Complexity of the Rainbow Subgraph Problem
- A threshold of ln n for approximating set cover
- Relations between average case complexity and approximation complexity
- Rainbow subgraphs in properly edge‐colored graphs
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Approximation Algorithms and Hardness for Domination with Propagation
- The dense \(k\)-subgraph problem
- On the hardness of approximating spanners
This page was built for publication: On the approximability of the minimum rainbow subgraph problem and other related problems
