The edge versus path incidence matrix of series-parallel graphs and greedy packing

DOI10.1016/S0166-218X(00)00294-8MaRDI QIDQ5951970zbMATH OpenFDO

Authors Alan J. Hoffman, Baruch Schieber

Publication date 28 August 2002

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

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00294-8

zbMATH Keywords

directed graphincidence matrixpacking problempathseries-parallel graphs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Review text

Suppose \(G\) is a series-parallel directed graph with endpoints \(s\) and \(t\). An edge-path incidence matrix \(A\) is a \((0,1)\) matrix in which each row corresponds to an edge of \(G\) and each column corresponds to a directed \((s,t)\) path. The \((i,j)\) element of \(A\) is 1 if edge \(i\) is in the \(j\) \((s,t)\) path; otherwise the element is 0. The authors characterize \(A\) structurally and algorithmically and note that the results relate to the max-flow problem in series-parallel graphs and a solution to a packing problem.

Recommendations

• Greedy packing and series-parallel graphs
• On greedy algorithms for series parallel graphs
• The path matrix of a graph, its construction and its use in evaluating certain products
• Packing paths in planar graphs
• Minimum-maximal matching in series-parallel graphs

Cites work

• Greedy packing and series-parallel graphs
• Minimum cost flow algorithms for series-parallel networks
• On simple combinatorial optimization problems. A collection of contributions in honour of Jack van Lint

Cited in

(4)

• Greedy packing and series-parallel graphs
• Theory and implementation of coalitional analysis in cooperative decision making
• Theory and application of conflict resolution with hybrid preference in colored graphs
• A matrix-based approach to searching colored paths in a weighted colored multidigraph

This page was built for publication: The edge versus path incidence matrix of series-parallel graphs and greedy packing

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