Hamiltonian problems in directed graphs with simple row patterns

DOI10.1016/J.TCS.2022.03.005MaRDI QIDQ2143132zbMATH OpenOpenAlexWikidataFDO

Authors Irena Rusu

Publication date 31 May 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.03.005

zbMATH Keywords

complexity of algorithmsconsecutive ones propertyHamiltonian problemslinear ordering of the vertices

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• A note on the Hamiltonian circuit problem on directed path graphs
• Hamiltonian cycles in circulant digraphs with two stripes
• On the existence of Hamilton cycles with a periodic pattern in a random digraph

Cites work

• A simplified NP-complete satisfiability problem
• A survey on Hamilton cycles in directed graphs
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Digraphs. Theory, algorithms and applications
• Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey
• Hamiltonian cycles in circulant digraphs with two stripes
• scientific article; zbMATH DE number 4204369 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 1286212 (Why is no real title available?)
• scientific article; zbMATH DE number 3046846 (Why is no real title available?)
• Interval digraphs: An analogue of interval graphs
• Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
• On hamiltonicity of circulant digraphs of outdegree three
• Permutation reconstruction from differences
• Some simplified NP-complete graph problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Hamiltonian property of consecutive-\(d\) digraphs
• The Hamiltonian property of linear functions
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(1)

• A note on the Hamiltonian circuit problem on directed path graphs

This page was built for publication: Hamiltonian problems in directed graphs with simple row patterns

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