Home > Research > Publications & Outputs > Simple Necessary Conditions for the Existence o...

Research

Electronic data

  • 1709.01367v1

    Accepted author manuscript, 130 KB, PDF document

Keywords

View graph of relations

Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs

Research output: Working paper › Preprint

Published

Standard

Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs. / Welke, Pascal.
Arxiv, 2017.

Research output: Working paper › Preprint

Harvard

Welke, P 2017 'Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs' Arxiv.

APA

Welke, P. (2017). Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs. Arxiv.

Vancouver

Welke P. Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs. Arxiv. 2017 Sept 5.

Author

Welke, Pascal. / Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs. Arxiv, 2017.

Bibtex

@techreport{ada367cdb77a49ab8da40b78472472c7,
title = "Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs",
abstract = "We describe some necessary conditions for the existence of a Hamiltonian path in any graph (in other words, for a graph to be traceable). These conditions result in a linear time algorithm to decide the Hamiltonian path problem for cactus graphs. We apply this algorithm to several molecular databases to report the numbers of graphs that are traceable cactus graphs. ",
keywords = "cs.DM",
author = "Pascal Welke",
note = "6 pages, 2 figures, presented 2014 at a student workshop at the University of Bonn",
year = "2017",
month = sep,
day = "5",
language = "English",
publisher = "Arxiv",
type = "WorkingPaper",
institution = "Arxiv",

}

RIS

TY - UNPB

T1 - Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs

AU - Welke, Pascal

N1 - 6 pages, 2 figures, presented 2014 at a student workshop at the University of Bonn

PY - 2017/9/5

Y1 - 2017/9/5

N2 - We describe some necessary conditions for the existence of a Hamiltonian path in any graph (in other words, for a graph to be traceable). These conditions result in a linear time algorithm to decide the Hamiltonian path problem for cactus graphs. We apply this algorithm to several molecular databases to report the numbers of graphs that are traceable cactus graphs.

AB - We describe some necessary conditions for the existence of a Hamiltonian path in any graph (in other words, for a graph to be traceable). These conditions result in a linear time algorithm to decide the Hamiltonian path problem for cactus graphs. We apply this algorithm to several molecular databases to report the numbers of graphs that are traceable cactus graphs.

KW - cs.DM

M3 - Preprint

BT - Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs

PB - Arxiv

ER -