Abstract | ||
---|---|---|
By definition, a P2-graph Γ is an undirected graph in which every vertex is contained in a path of length two. For such a graph, pc(Γ) denotes the minimum number of paths of length two that cover all n vertices of Γ. We prove that ⌈n/3⌉≤pc(Γ)≤⌊n/2⌋ and show that these upper and lower bounds are tight. Furthermore we show that every connected P2-graph Γ contains a spanning tree T such that pc(Γ)=pc(T). We present a linear time algorithm that produces optimal 2-path covers for trees. This is contrasted by the result that the decision problem pc(Γ)=?n/3 is NP-complete for trivalent graphs. This graph theoretical problem originates from the task of searching a large database of biological molecules such as the Protein Data Bank (PDB) by content. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1016/j.dam.2007.11.021 | Discrete Applied Mathematics |
Keywords | DocType | Volume |
Covering problems,2-path cover,Edge cover,Optimal tree cover,Tiling problems,Trivalent graphs | Journal | 156 |
Issue | ISSN | Citations |
15 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Rolf Bardeli | 1 | 69 | 8.09 |
Michael Clausen | 2 | 469 | 43.66 |
Andreas Ribbrock | 3 | 16 | 2.46 |