Linear algorithm for optimal path cover problem on interval graphs
From MaRDI portal
Publication:911770
DOI10.1016/0020-0190(90)90064-5zbMath0697.68048OpenAlexW2054496228MaRDI QIDQ911770
C. Pandu Rangan, Srinivasa Rao Arikati
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(90)90064-5
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Related Items (49)
Algorithms for finding disjoint path covers in unit interval graphs ⋮ On the \(k\)-path cover problem for cacti ⋮ The path-partition problem in block graphs ⋮ Solving the maximum internal spanning tree problem on interval graphs in polynomial time ⋮ Deferred-query—An efficient approach for problems on interval and circular-arc graphs ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ Hole: An Emerging Character in the Story of Radio k-Coloring Problem ⋮ Unnamed Item ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Disjoint path covers with path length constraints in restricted hypercube-like graphs ⋮ \(k\)-path partitions in trees ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ On the \(k\)-path partition of graphs. ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Linear-time certifying algorithms for the path cover and Hamiltonian cycle problems on interval graphs ⋮ Isomorphic coupled-task scheduling problem with compatibility constraints on a single processor ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Optimal path cover problem on block graphs ⋮ Torus-like graphs and their paired many-to-many disjoint path covers ⋮ Path covering number and \(L(2,1)\)-labeling number of graphs ⋮ A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ Vertex partitions of \(r\)-edge-colored graphs ⋮ The longest cycle problem is polynomial on interval graphs ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ Finding a minimum path cover of a distance-hereditary graph in polynomial time ⋮ The harmonious coloring problem is NP-complete for interval and permutation graphs ⋮ On characterizing radio \(k\)-coloring problem by path covering problem ⋮ Local search algorithms for finding the Hamiltonian completion number of line graphs ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ Path partition for graphs with special blocks ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Nontrivial path covers of graphs: existence, minimization and maximization ⋮ A Polynomial Time Algorithm for Longest Paths in Biconvex Graphs ⋮ Optimal path cover problem on block graphs and bipartite permutation graphs ⋮ Jump number maximization for proper interval graphs and series-parallel graphs ⋮ An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs ⋮ Partial and perfect path covers of cographs ⋮ The Steiner cycle and path cover problem on interval graphs ⋮ The approximability of the weighted Hamiltonian path completion problem on a tree ⋮ 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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
- Finding Hamiltonian circuits in interval graphs
- A unified approach to domination problems on interval graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Minimum node disjoint path covering for circular-arc graphs
- Linear algorithm for domatic number problem on interval graphs
- Advances on the Hamiltonian Completion Problem
This page was built for publication: Linear algorithm for optimal path cover problem on interval graphs
