Sequence Hypergraphs

DOI10.1007/978-3-662-53536-3_24zbMath1417.05144OpenAlexW2913456588MaRDI QIDQ3181065

Guido Proietti, Kateřina Böhmová, Matúš Mihalák, Jérémie Chalopin, Peter Widmayer

Publication date: 22 December 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53536-3_24

zbMATH Keywords

complexityalgorithmscolored graphsoriented hypergraphslabeled problems

Mathematics Subject Classification ID

Hypergraphs (05C65) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation and hardness results for label cut and related problems
• Intersecting Sperner families and their convex hulls
• A generalization of rotational tournaments
• On the minimum label spanning tree problem
• Directed hypergraphs and applications
• Approximation algorithms and hardness results for labeled connectivity problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Hamiltonian paths and cycles in hypertournaments
• Shortest Paths with Bundles and Non-additive Weights Is Hard
• Computing and Listing st-Paths in Public Transportation Networks
• The Parameterized Complexity of Some Minimum Label Problems