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)
68R10: Graph theory (including graph drawing) in computer science
05C45: Eulerian and Hamiltonian graphs
Related Items
Unnamed Item, Unnamed Item, Kernelization of Two Path Searching Problems on Split Graphs, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs, Vertex Deletion Problems on Chordal Graphs, Combinatorics and algorithms for quasi-chain graphs, Combinatorics and algorithms for quasi-chain graphs, Intersection graphs of non-crossing paths, 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, Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs, 2-Trees: Structural insights and the study of Hamiltonian paths, Path eccentricity of graphs, Sequentially swapping tokens: further on graph classes, On 3-degree 4-chordal graphs, Contracting to a longest path in H-free graphs, Detour trees, Computing role assignments of split graphs, Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs, Boundary properties of graphs for algorithmic graph problems, 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, The longest path problem has a polynomial solution on interval graphs, Hamiltonian properties of locally connected graphs with bounded vertex degree, Edge cover by connected bipartite subgraphs, Linear-time algorithm for the paired-domination problem in convex bipartite graphs, Nonempty intersection of longest paths in series-parallel graphs, On the terminal connection problem, Cyclability in graph classes, Finding Hamiltonian circuits in quasi-adjoint graphs, On the \(k\)-path partition of graphs., Tractabilities and intractabilities on geometric intersection graphs, Path partition for graphs with special blocks, Vertex deletion problems on chordal graphs, Chordal bipartite graphs of bounded tree- and clique-width, The longest path problem is polynomial on cocomparability graphs, Exact algorithms for finding longest cycles in claw-free graphs, The 1-fixed-endpoint path cover problem is Polynomial on interval 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 maximum-weight induced matchings and minimum chain covers in convex bipartite graphs, Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph, Well-partitioned chordal graphs, Mim-width. I. Induced path problems, On strictly chordality-\(k\) graphs, Complexity-separating graph classes for vertex, edge and total colouring, A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs, The complexity of dissociation set problems in graphs, Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite 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, A multivariate analysis of the strict terminal connection problem, Linear structure of bipartite permutation graphs and the longest path problem, Boundary classes for graph problems involving non-local properties, On the minimum eccentricity shortest path problem, Lower bounds on the mim-width of some graph classes, NP-hard graph problems and boundary classes of graphs, Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs, Complexity of Hamiltonian cycle reconfiguration, On the kernelization of split graph problems, New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs, Minimum Eccentricity Shortest Paths in Some Structured Graph Classes, Hamiltonicity in Split Graphs - A Dichotomy, The Longest Path Problem is Polynomial on Cocomparability Graphs, ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES, The Longest Path Problem Is Polynomial on Interval Graphs, On the Minimum Eccentricity Shortest Path Problem, The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
