On finding the longest antisymmetric path in directed acyclic graphs

DOI10.1016/J.IPL.2014.10.014MaRDI QIDQ477694zbMATH OpenOpenAlexFDO

Authors Yinglei Song, Menghong Yu

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

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

Recommendations

• Antipaths in oriented graphs
• Path problems in skew-symmetric graphs
• scientific article; zbMATH DE number 1003285
• On approximating the longest path in a graph
• Automata, Languages and Programming
• Finding a Longest Path in a Complete Multipartite Digraph
• scientific article; zbMATH DE number 4025473
• Longest paths and cycles in bipartite oriented graphs
• On approximating the longest path in a graph
• Graph-Theoretic Concepts in Computer Science

Cites work

• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Approximation algorithms for combinatorial problems
• Impossible pair constrained test path generation in a program
• Linear FPT reductions and computational lower bounds
• On the complexity of paths avoiding forbidden pairs
• 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
• The importance of being biased

Cited in

(1)

• Peptide sequencing via graph path decomposition

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

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