Publication

Finding Hamiltonian circuits in quasi-adjoint graphs

Dominique de Werra, Benjamin Leroy-Beaulieu
2008
Conference Papers

Abstract

This paper is motivated by a method used for DNA sequencing by hybridization presented in [Jacek Blazewicz, Marta Kasprzak, Computational complexity of isothernnic DNA sequencing by hybridization, Discrete Appl. Math. 154 (5) (2006) 718-7291. This paper presents a class of digraphs: the quasi-adjoint graphs. This class includes the ones used in the paper cited above. A polynomial recognition algorithm in O(n(3)), as well as a polynomial algorithm in O(n(2) + m(2)) for finding a Hamiltonian circuit in these graphs are given. Furthermore, some results about related problems such as finding a Eulerian circuit while respecting some forbidden transitions (a path with three vertices) are discussed. (c) 2008 Elsevier B.V. All rights reserved.

Official source

https://infoscience.epfl.ch/entities/publication/23925710-95df-41e3-a797-72d62ea89684

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Dominique de Werra, Benjamin Leroy-Beaulieu
2008
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/23925710-95df-41e3-a797-72d62ea89684

About this result

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Hamiltonian path

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.

Hamiltonian path problem

In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a Hamiltonian cycle exists in a given graph (whether directed or undirected). Both problems are NP-complete.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Related publications (30)

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Colin Peter Sandon

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

Ieee-Inst Electrical Electronics Engineers Inc2024

Non-planarity of Markoff graphs mod p

Matthew De Courcy-Ireland

We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...

European Mathematical Soc-Ems2024

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

Lukas Fritz Felix Vogl

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024