The path-partition problem in block graphs

DOI10.1016/0020-0190(94)00158-8zbMath0938.68756OpenAlexW1981160730MaRDI QIDQ1342260

Jing-Ho Yan, Gerard Jennhwa Chang

Publication date: 21 June 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://ntur.lib.ntu.edu.tw/bitstream/246246/181388/1/32.pdf

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On the \(k\)-path cover problem for cacti, Unnamed Item, \(k\)-path partitions in trees, Optimal path cover problem on block graphs, 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., Vertex partitions of \(r\)-edge-colored graphs, Finding a minimum path cover of a distance-hereditary graph in polynomial time, Path partition for graphs with special blocks, The approximability of the weighted Hamiltonian path completion problem on a tree, Corrigendum to ``The path-partition problem in block graphs., Solving the path cover problem on circular-arc graphs by using an approximation algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Linear algorithm for optimal path cover problem on interval graphs
• Hamiltonian cycle is polynomial on cocomparability graphs
• Minimum node disjoint path covering for circular-arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Hamiltonian circuits and path coverings of vertices in graphs
• The $L(2,1)$-Labeling Problem on Graphs