<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs

descriptionPublicationkeyboard_double_arrow_right Article 01 Jan 1993 Denmark Publisher:Elsevier BVJournal:Discrete Applied Mathematics, volume 41, pages 75-79 (issn: 0166-218X,

Authors: Bang-Jensen, J.; Hell, P.;

doi: 10.1016/0166-218x(93)90246-k

Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs

- Summary
- Subjects
- Related research
  (6)
- Metrics

Abstract

A tournament is an oriented digraph in which every pair of vertices is joined by an arc. An in-tournament digraph is a digraph in which the set of in-neighbours of each vertex induces a tournament. This note gives an \(O(m+n\log n)\) algorithm for finding a longest path and cycle in an in- tournament digraph, where \(m\) and \(n\) are the numbers of arcs respectively vertices of the in-tournament digraph.

Country

Denmark

Related Organizations

Keywords

Eulerian and Hamiltonian graphs, algorithm, cycle, Applied Mathematics, Directed graphs (digraphs), tournaments, path, tournament, Graph algorithms (graph-theoretic aspects), in-tournament digraph, Discrete Mathematics and Combinatorics, Paths and cycles

6 Research products, page 1 of 1

Pancyclic orderings of in-tournaments
1999IsAmongTopNSimilarDocuments
Completing orientations of partially oriented graphs
2017IsAmongTopNSimilarDocuments
Local tournaments and in-tournaments
2007IsAmongTopNSimilarDocuments
Pancyclic in-tournaments
2001IsAmongTopNSimilarDocuments
On the Complexity of Singly Connected Vertex Deletion
2020IsAmongTopNSimilarDocuments
Vertex 6-pancyclic in-tournaments
2004IsAmongTopNSimilarDocuments

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average