On finding the longest antisymmetric path in directed acyclic graphs

DOI10.1016/j.ipl.2014.10.014zbMath1302.68129OpenAlexW2050947816MaRDI QIDQ477694

Menghong Yu, Yinglei Song

Publication date: 9 December 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2014.10.014

zbMATH Keywords

computational complexitylower boundinapproximabilitydirected acyclic graphslongest antisymmetric path

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Peptide sequencing via graph path decomposition

Cites Work

• Unnamed Item
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• On the complexity of paths avoiding forbidden pairs
• Approximation algorithms for combinatorial problems
• Impossible pair constrained test path generation in a program
• The importance of being biased
• Linear FPT reductions and computational lower bounds

This page was built for publication: On finding the longest antisymmetric path in directed acyclic graphs