On finding the longest antisymmetric path in directed acyclic graphs

DOI10.1016/J.IPL.2014.10.014zbMATH Open1302.68129OpenAlexW2050947816MaRDI QIDQ477694FDOQ477694

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

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

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)

Cites Work

• Approximation algorithms for combinatorial problems
• Title not available (Why is that?)
• On the complexity of paths avoiding forbidden pairs
• Linear FPT reductions and computational lower bounds
• The importance of being biased
• 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
• Impossible pair constrained test path generation in a program

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)