Name
Abstract | ||
|---|---|---|
AbstractWe prove that the weak k-linkage problem is polynomial for every fixed k for totally ï -decomposable digraphs, under appropriate hypothesis on ï . We then apply this and recent results by Fradkin and Seymour on the weak k-linkage problem for digraphs of bounded independence number or bounded cut-width to get polynomial algorithms for some classes of digraphs like quasi-transitive digraphs, extended semicomplete digraphs, locally semicomplete digraphs all of which contain the class of semicomplete digraphs as a subclass and directed cographs. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1002/jgt.21775 | Periodicals |
Keywords | Field | DocType |
weak linkages,modular partition,decomposable digraph,locally semicomplete digraph,quasi-transitive digraph,arc-disjoint paths,cut-width | Discrete mathematics,Topology,Combinatorics,Independence number,Arc (geometry),Disjoint sets,Polynomial,Polynomial algorithm,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
77 | 2 | 0364-9024 |
Citations | PageRank | References |
3 | 0.41 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jørgen Bang-Jensen | 1 | 9 | 2.01 |
| Alessandro Maddaloni | 2 | 10 | 2.09 |