HAMILTONian circuits in chordal bipartite graphs
From MaRDI portal
Publication:1923528
DOI10.1016/0012-365X(95)00057-4zbMath0856.68113MaRDI QIDQ1923528
Publication date: 13 November 1996
Published in: Discrete Mathematics (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Related Items (74)
Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ Detour trees ⋮ Computing role assignments of split graphs ⋮ On the terminal connection problem ⋮ Cyclability in graph classes ⋮ On the Minimum Eccentricity Shortest Path Problem ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Well-partitioned chordal graphs ⋮ Linear structure of bipartite permutation graphs and the longest path problem ⋮ On the kernelization of split graph problems ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Boundary classes for graph problems involving non-local properties ⋮ On the minimum eccentricity shortest path problem ⋮ Mim-width. I. Induced path problems ⋮ On strictly chordality-\(k\) graphs ⋮ Lower bounds on the mim-width of some graph classes ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ Some results on connected vertex separators ⋮ On the computational difficulty of the terminal connection problem ⋮ Broadcasting in split graphs ⋮ Assistance and interdiction problems on interval graphs ⋮ Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ On the \(k\)-path partition of graphs. ⋮ Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs ⋮ 2-Trees: Structural insights and the study of Hamiltonian paths ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Path eccentricity of graphs ⋮ Sequentially swapping tokens: further on graph classes ⋮ On 3-degree 4-chordal graphs ⋮ Hamiltonicity in Split Graphs - A Dichotomy ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Hamiltonian properties of locally connected graphs with bounded vertex degree ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Edge cover by connected bipartite subgraphs ⋮ Kernelization of Two Path Searching Problems on Split Graphs ⋮ Tractabilities and intractabilities on geometric intersection graphs ⋮ NP-hard graph problems and boundary classes of graphs ⋮ Contracting to a longest path in H-free graphs ⋮ Finding Hamiltonian circuits in quasi-adjoint graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Path partition for graphs with special blocks ⋮ Boundary properties of graphs for algorithmic graph problems ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ Intersection graphs of non-crossing paths ⋮ The complexity of dissociation set problems in graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ Vertex deletion problems on chordal graphs ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ Nonempty intersection of longest paths in series-parallel graphs ⋮ Cospectral bipartite graphs with the same degree sequences but with different number of large cycles ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs ⋮ A multivariate analysis of the strict terminal connection problem ⋮ Minimum Eccentricity Shortest Paths in Some Structured Graph Classes ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Chordal bipartite graphs of bounded tree- and clique-width ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ On the recognition of search trees generated by BFS and DFS ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ Revising Johnson's table for the 21st century ⋮ Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs ⋮ Vertex Deletion Problems on Chordal Graphs ⋮ Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs
- Finding Hamiltonian circuits in proper interval graphs
- Characterizations of strongly chordal graphs
- Finding Hamiltonian circuits in interval graphs
- Hamiltonian circuits in interval graph generalizations
- Bipartite permutation graphs
- Complement reducible graphs
- Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
- Planar Formulae and Their Uses
- Some Examples of Difficult Traveling Salesman Problems
- Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
- Hamilton Paths in Grid Graphs
This page was built for publication: HAMILTONian circuits in chordal bipartite graphs
