Optimal path cover problem on block graphs

DOI10.1016/S0304-3975(98)00180-7MaRDI QIDQ1960660zbMATH OpenFDO

Authors Wong, Pak-ken

Publication date 12 January 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(98)00180-7

zbMATH Keywords

block graphend blockextreme cut vertexminimum path partitionremovable edge

Mathematics Subject Classification ID

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

Recommendations

• Path partition for graphs with special blocks
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Induced-path partition on graphs with special blocks
• An optimal path cover algorithm for cographs
• Efficient algorithms for path partitions

Cites work

• Graph theory
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 3517192 (Why is no real title available?)
• Linear algorithm for optimal path cover problem on interval graphs
• Minimum node disjoint path covering for circular-arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• The path-partition problem in block graphs

Cited in

(18)

• Optimal path cover problem on block graphs and bipartite permutation graphs
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• Path partition for graphs with special blocks
• Corrigendum to ``The path-partition problem in block graphs.
• An optimal path cover algorithm for cographs
• Algorithms for maximum internal spanning tree problem for some graph classes
• Proof that pyramid networks are 1-Hamiltonian-connected with high probability
• Path covering number and \(L(2,1)\)-labeling number of graphs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Node-searching problem on block 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
• On the dominator coloring in proper interval graphs and block graphs
• Algorithms for solving problems on graphs of bounded pathwidth
• On the path partition number of 6‐regular graphs
• Induced-path partition on graphs with special blocks
• Optimal vertex ranking of block graphs
• The pos/neg-weighted median problem on block graphs with subgraph-shaped customers

This page was built for publication: Optimal path cover problem on block graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1960660)