Path partition for graphs with special blocks

DOI10.1016/J.DAM.2004.03.006MaRDI QIDQ1765521zbMATH OpenOpenAlexFDO

Authors Gerard Jennhwa Chang, Junjie Pan

Publication date 23 February 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.03.006

zbMATH Keywords

AlgorithmBlockComplete bipartite graphComplete graphCyclePath partition

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Optimal path cover problem on block graphs
• \(k\)-path partitions in trees
• On the \(k\)-path partition of graphs.
• Induced-path partition on graphs with special blocks
• On the k-path partition problem in cographs

Cites work

• \(k\)-path partitions in trees
• Algorithmic aspects of linear k-arboricity
• An optimal path cover algorithm for cographs
• Complement reducible graphs
• Corrigendum to ``The path-partition problem in block graphs.
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Hamiltonian circuits and path coverings of vertices in graphs
• HAMILTONian circuits in chordal bipartite graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Isometric-path numbers of block graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Minimum node disjoint path covering for circular-arc graphs
• On a class of posets and the corresponding comparability graphs
• Optimal path cover problem on block graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Paths in interval graphs and circular arc graphs
• The $L(2,1)$-Labeling Problem on Graphs
• The path-partition problem in bipartite distance-hereditary graphs
• The path-partition problem in block graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(14)

• Optimal path cover problem on block graphs and bipartite permutation graphs
• Partitioning graphs into Hamiltonian ones
• \(k\)-path partitions in trees
• On the \(k\)-path partition of graphs.
• Efficient algorithms for path partitions
• Optimal path cover problem on block graphs
• The community structure of human cellular signaling network
• Graphs with a path partition for structuring digital spaces
• On the k-path partition problem in cographs
• Minimum height path partitioning of trees
• Parameterizing path partitions
• Polynomial-time algorithms for \textsc{Path Cover} on trees and graphs of bounded treewidth
• Polynomial-time algorithms for \textsc{Path Cover} and \textsc{Path Partition} on trees and graphs of bounded treewidth
• Induced-path partition on graphs with special blocks

This page was built for publication: Path partition for graphs with special blocks

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