On the \(k\)-path partition of graphs.

DOI10.1016/S0304-3975(02)00577-7zbMath1044.68134MaRDI QIDQ1401225

George Steiner

Publication date: 17 August 2003

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

zbMATH Keywords

bipartite permutation graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (23)

Parameterized Complexity of $$(A,\ell )$$-Path Packing ⋮ On the \(k\)-path cover problem for cacti ⋮ On the complexity of the \(k\)-customer vehicle routing problem ⋮ Proof that pyramid networks are 1-Hamiltonian-connected with high probability ⋮ Path cover problems with length cost ⋮ Unnamed Item ⋮ Parameterizing path partitions ⋮ Approximation algorithms for the directed path partition problems ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Approximating the directed path partition problem ⋮ Approximation results for the weighted \(P_4\) partition problem ⋮ The path partition problem and related problems in bipartite graphs ⋮ Star Partitions of Perfect Graphs ⋮ Path cover problems with length cost ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ A boundary class for the \(k\)-path partition problem ⋮ A local search algorithm for binary maximum 2-path partitioning ⋮ On the existence of a cyclic near-resolvable \((6n+4)\)-cycle system of \(2 K_{12n+9}\) ⋮ Labeling bipartite permutation graphs with a condition at distance two ⋮ Unnamed Item ⋮ The local partition dimension of graphs ⋮ A complexity and approximation framework for the maximization scaffolding problem ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear algorithm for optimal path cover problem on interval graphs
• Bipartite permutation graphs
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• Optimal chain partitions of trees
• Minimum node disjoint path covering for circular-arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• \(k\)-path partitions in trees
• An optimal path cover algorithm for cographs
• Cardinality-restricted chains and antichains in partially ordered sets
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits and path coverings of vertices in graphs
• Graph Classes: A Survey
• The $L(2,1)$-Labeling Problem on Graphs

This page was built for publication: On the \(k\)-path partition of graphs.