Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs

DOI10.1016/j.tcs.2018.12.007zbMath1422.68185arXiv1705.02124OpenAlexW2684179771WikidataQ128766521 ScholiaQ128766521MaRDI QIDQ2419108

Tamás Róbert Mezei, Lucas Colucci, Ervin Gyoeri, Péter L. Erdős

Publication date: 29 May 2019

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

Full work available at URL: https://arxiv.org/abs/1705.02124

zbMATH Keywords

complete bipartite graphedge-disjoint pathsterminal-pairability

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A minimum degree condition forcing complete graph immersion
• The disjoint paths problem in quadratic time
• Length 3 edge-disjoint paths is NP-hard
• Note on the diameter of path-pairable graphs
• Note on terminal-pairability in complete grid graphs
• An improved upper bound on the maximum degree of terminal-pairable complete graphs
• On path-pairability in the Cartesian product of graphs
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• The maximum edge-disjoint paths problem in complete graphs
• Graph minors XXIII. Nash-Williams' immersion conjecture
• Three-regular path pairable graphs
• On search, decision, and the efficiency of polynomial-time algorithms
• A communication problem and directed triple systems
• Terminal-pairability in complete bipartite graphs
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• Frustrated triangles
• Constructing Graphs with No Immersion of Large Complete Graphs
• Graph Coloring and the Immersion Order
• Terminal-Pairability in Complete Graphs
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Networks communicating for each pairing of terminals
• On the Complexity of Timetable and Multicommodity Flow Problems
• Complete graph immersions and minimum degree
• A Theorem on Coloring the Lines of a Network
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs