The complexity of finding certain trees in tournaments

DOI10.1007/3-540-57155-8_243MaRDI QIDQ5060108zbMATH OpenOpenAlexFDO

Authors R. Balasubramanian, Venkatesh Raman, G. Srinivasaraghavan

Publication date 18 January 2023

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

Full work available at URL https://doi.org/10.1007/3-540-57155-8_243

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding Scores in Tournaments
• Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs
• The complexity of finding generalized paths in tournaments
• Tight bounds for finding degrees from the adjacency matrix
• Elusiveness of finding degrees

Cites work

• Antidirected Hamiltonian circuits in tournaments
• Antidirected Hamiltonian paths in tournaments
• Antidirected Hamiltonian paths in tournaments
• scientific article; zbMATH DE number 3902692 (Why is no real title available?)
• Parity of paths and circuits in tournaments
• Realization of certain generalized paths in tournaments
• The complexity of finding generalized paths in tournaments

Cited in

(11)

• Elusiveness of finding degrees
• Elusiveness of finding degrees
• scientific article; zbMATH DE number 1823770 (Why is no real title available?)
• The complexity of finding generalized paths in tournaments
• Finding Scores in Tournaments
• Tight bounds for finding degrees from the adjacency matrix
• Sublinear-Time Algorithms for Tournament Graphs
• Algorithms for finding maximum transitive subtournaments
• Sublinear-time algorithms for tournament graphs
• An optimal algorithm to find champions of tournament graphs
• Finding and counting small tournaments in large tournaments

This page was built for publication: The complexity of finding certain trees in tournaments

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