Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem

DOI10.1007/978-3-319-19315-1_2zbMath1396.68051OpenAlexW788730291WikidataQ58203674 ScholiaQ58203674MaRDI QIDQ2946037

Alexandru Popa, Anna Adamaszek, Guillaume Blin

Publication date: 15 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-19315-1_2

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (1)

Parameterized complexity and approximation issues for the colorful components problems

Cites Work

• Unnamed Item
• Algorithmic and hardness results for the colorful components problems
• The multi-multiway cut problem
• The hardness of approximation: Gap location
• Partitioning into Colorful Components by Minimum Edge Deletions
• Some Results on more Flexible Versions of Graph Motif
• OMG! Orthologs in Multiple Genomes – Competing Graph-Theoretical Formulations
• Approximation Algorithms for Some Graph Partitioning Problems

This page was built for publication: Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem