Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
From MaRDI portal
Publication:4302282
DOI10.1137/S0097539791200375zbMath0811.05043MaRDI QIDQ4302282
George Steiner, Jitender S. Deogun
Publication date: 14 August 1994
Published in: SIAM Journal on Computing (Search for Journal in Brave)
polynomial time algorithmpartially ordered setspermutation graphscocomparability graphhamiltonian cycle
Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)
Related Items
Cyclability in graph classes, Happy set problem on subclasses of co-comparability graphs, Unnamed Item, 1-tough cocomparability graphs are hamiltonian, A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, Vertex deletion into bipartite permutation graphs, Toughness, hamiltonicity and split graphs, Independent sets in asteroidal triple-free graphs, Mim-width. I. Induced path problems, Weighted domination of cocomparability graphs, HAMILTONian circuits in chordal bipartite graphs, Complete edge-colored permutation graphs, Complexity-separating graph classes for vertex, edge and total colouring, On the intersection of tolerance and cocomparability graphs, The longest path problem is polynomial on cocomparability graphs, Succinct permutation graphs, Hamiltonian properties of locally connected graphs with bounded vertex degree, Computing and counting longest paths on circular-arc graphs in polynomial time, Finding Hamiltonian circuits in quasi-adjoint graphs, Happy set problem on subclasses of co-comparability graphs, Vertex deletion into bipartite permutation graphs, An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs, The Longest Path Problem is Polynomial on Cocomparability Graphs, New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs, Jump number maximization for proper interval graphs and series-parallel graphs, Partial and perfect path covers of cographs, Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, AN ALGORITHM FOR FINDING LONGEST CYCLES IN CERTAIN BIPARTITE GRAPHS, Revising Johnson's table for the 21st century, Hamiltonian powers in threshold and arborescent comparability graphs, Solving the path cover problem on circular-arc graphs by using an approximation algorithm, Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs
