Search results for "edge-disjoint"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
85	Amitabha Bagchi, Amitabh Chaudhary, Christian Scheideler, Petr Kolman	Algorithms for fault-tolerant routing in circuit switched networks.	SPAA	2002	DBLP DOI BibTeX RDF	flow number, greedy algorithms, fault-tolerant routing, multicommodity flow, edge-disjoint paths
75	Ken-ichi Kawarabayashi, Bruce A. Reed	Odd cycle packing.	STOC	2010	DBLP DOI BibTeX RDF	odd cycle, packing
75	Xiao Zhou 0001, Syurei Tamura, Takao Nishizeki	Finding Edge-Disjoint Paths in Partial k-Trees.	Algorithmica	2000	DBLP DOI BibTeX RDF	Polynomial-time algorithm, Edge-coloring, Edge-disjoint paths, Partial k -tree, Bounded treewidth
75	Xiao Zhou 0001, Syurei Tamura, Takao Nishizeki	Finding Edge-Disjoint Paths in Partial k-Trees (Extended Abstract).	ISAAC	1996	DBLP DOI BibTeX RDF	bounded tree-width, polynomial-time algorithm, edge-coloring, edge-disjoint paths, partial k-tree
63	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	Edge-disjoint paths in Planar graphs with constant congestion.	STOC	2006	DBLP DOI BibTeX RDF	Planar graphs, multicommodity flow, edge-disjoint paths
63	Qian-Ping Gu, Hisao Tamaki	Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths.	IPPS	1996	DBLP DOI BibTeX RDF	algorithm, Permutation routing, edge-disjoint paths, circuit-switched networks
59	Torsten Tholey	Solving the 2-Disjoint Paths Problem in Nearly Linear Time.	Theory Comput. Syst.	2006	DBLP DOI BibTeX RDF
59	Torsten Tholey	Solving the 2-Disjoint Paths Problem in Nearly Linear Time.	STACS	2004	DBLP DOI BibTeX RDF
58	Peng Zhang 0008, Wenbo Zhao 0001	On the Complexity and Approximation of the Min-Sum and Min-Max Disjoint Paths Problems.	ESCAPE	2007	DBLP DOI BibTeX RDF
54	Matthew Andrews, Lisa Zhang	Logarithmic hardness of the undirected edge-disjoint paths problem.	J. ACM	2006	DBLP DOI BibTeX RDF	Hardness of approximation, undirected graphs, edge-disjoint paths
54	Matthew Andrews, Lisa Zhang	Hardness of the undirected edge-disjoint paths problem.	STOC	2005	DBLP DOI BibTeX RDF	hardness of approximation, undirected graphs, edge-disjoint paths
53	Mohammad R. Salavatipour, Jacques Verstraëte	Disjoint Cycles: Integrality Gap, Hardness, and Approximation.	IPCO	2005	DBLP DOI BibTeX RDF
52	Myung M. Bae, Bella Bose	Edge Disjoint Hamiltonian Cycles in k-Ary n-Cubes and Hypercubes.	IEEE Trans. Computers	2003	DBLP DOI BibTeX RDF	Lee distance Gray codes, binary Gray codes, hypercube, Hamiltonian cycle, k-ary n-cubes, Lee distance
50	Michael Krivelevich, Zeev Nutov, Mohammad R. Salavatipour, Jacques Verstraëte, Raphael Yuster	Approximation algorithms and hardness results for cycle packing problems.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Cycle packing, edge-disjoint, approximation algorithms, hardness of approximation, integrality gap
49	Ruen Chze Loh, Sieteng Soh, Mihai M. Lazarescu, Suresh Rai	A Greedy Technique for Finding the Most Reliable Edge-Disjoint-Path-Set in a Network.	PRDC	2008	DBLP DOI BibTeX RDF
48	Chandra Chekuri, Sanjeev Khanna	Edge-disjoint paths revisited.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	multicommodity flow relaxation, approximation algorithm, greedy algorithm, Edge-disjoint paths
48	Mingji Xia	Maximum Edge-Disjoint Paths Problem in Planar Graphs.	TAMC	2007	DBLP DOI BibTeX RDF	maximum edge-disjoint paths, #P-hard, determinant
48	Jan M. Hochstein, Karsten Weihe	Edge-disjoint routing in plane switch graphs in linear time.	J. ACM	2004	DBLP DOI BibTeX RDF	Planar graphs, edge-disjoint paths
48	Shan-Chyun Ku, Biing-Feng Wang, Ting-Kai Hung	Constructing Edge-Disjoint Spanning Trees in Product Networks.	IEEE Trans. Parallel Distributed Syst.	2003	DBLP DOI BibTeX RDF	Cartesian product networks, edge-disjoint trees, fault-tolerance, interconnection networks, embedding, spanning trees
48	Aravind Srinivasan	Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems.	FOCS	1997	DBLP DOI BibTeX RDF	multi-commodity flow relaxation, multiprocessor interconnection networks, edge-disjoint paths, unsplittable flow, routing problems
47	Paraskevi Fragopoulou, Selim G. Akl	Fault tolerant communication algorithms on the star network using disjoint paths.	HICSS (2)	1995	DBLP DOI BibTeX RDF	fault-tolerant communication algorithms, node pairs, directed edge-disjoint spanning trees, single-node broadcasting, multinode broadcasting, single-node scattering problem, all-port communication assumption, faulty edges, multinode scattering problem, interconnection networks, fault tolerant computing, broadcasting, graph, multiprocessor interconnection networks, trees (mathematics), disjoint paths, star network, message transmission, faulty nodes
45	Zachary Friggstad, Mohammad R. Salavatipour	Approximability of Packing Disjoint Cycles.	ISAAC	2007	DBLP DOI BibTeX RDF
45	Jenn-Yang Tien, Ching-Tien Ho, Wei-Pang Yang	Broadcasting on incomplete hypercubes.	SPDP	1991	DBLP DOI BibTeX RDF
44	Ashkan Aazami, Joseph Cheriyan, Krishnam Raju Jampani	Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
44	Andreas Schwill	Shorest Edge-Disjoint Paths in Graphs.	STACS	1989	DBLP DOI BibTeX RDF
43	Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang	Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.	FOCS	2005	DBLP DOI BibTeX RDF
43	Arch D. Robison	A group of permutations with edge-disjoint paths on hypercubes.	SPDP	1991	DBLP DOI BibTeX RDF
41	Pallavi Manohar, V. Sridhar	Routing, Wavelength Assignment in Optical Networks Using an Efficient and Fair EDP Algorithm.	International Conference on Computational Science	2004	DBLP DOI BibTeX RDF	Edge Disjoint Path Algorithms, Optical Networks, Routing and Wavelength Assignment
41	Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi	Fast edge splitting and Edmonds' arborescence construction for unweighted graphs.	SODA	2008	DBLP BibTeX RDF
40	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	Edge-Disjoint Paths in Planar Graphs.	FOCS	2004	DBLP DOI BibTeX RDF
40	Satish Rao, Shuheng Zhou	Edge Disjoint Paths in Moderately Connected Graphs.	ICALP (1)	2006	DBLP DOI BibTeX RDF
39	Paraskevi Fragopoulou, Selim G. Akl	Edge-Disjoint Spanning Trees on the Star Network with Applications to Fault Tolerance.	IEEE Trans. Computers	1996	DBLP DOI BibTeX RDF	edge-disjoint trees, fault tolerance, parallel algorithm, interconnection network, spanning tree, star network, Communication algorithm
38	Naoki Katoh, Shin-ichi Tanigawa	A proof of the molecular conjecture.	SCG	2009	DBLP DOI BibTeX RDF	bar-and-joint frameworks, body-and-hinge frameworks, edge-disjoint spanning trees, the molecular conjecture, rigidity
38	Abdelfattah Abouelaoualim, Kinkar Chandra Das, Luérbio Faria, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad	Paths and Trails in Edge-Colored Graphs.	LATIN	2008	DBLP DOI BibTeX RDF	properly edge-colored paths, trails and cycles, connectivity, Edge colored graphs
38	Spyros Tragoudas, Yaakov L. Varol	Computing Disjoint Path with Lenght Constraints.	WG	1996	DBLP DOI BibTeX RDF
34	Dirk Müller 0003	On the complexity of the planar directed edge-disjoint paths problem.	Math. Program.	2006	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 05C38, 68Q17, 68R10, 90C35
34	Chien-Hung Huang, Jywe-Fei Fang, Chin-Yang Yang	Edge-Disjoint Hamiltonian Cycles of WK-Recursive Networks.	PARA	2004	DBLP DOI BibTeX RDF
34	Maria J. Blesa, Christian Blum 0001	Ant Colony Optimization for the Maximum Edge-Disjoint Paths Problem.	EvoWorkshops	2004	DBLP DOI BibTeX RDF
34	Hyunseung Choo, Vladimir V. Shakhov	Routing and Wavelength Assignments in Optical WDM Networks with Maximum Quantity of Edge Disjoint Paths.	International Conference on Computational Science	2004	DBLP DOI BibTeX RDF
34	R. Sai Anand, Thomas Erlebach	On-line Algorithms for Edge-Disjoint Paths in Trees of Rings.	LATIN	2002	DBLP DOI BibTeX RDF
34	Thomas Erlebach, Klaus Jansen	Implementation of Approximation Algorithms for Weighted and Unweighted Edge-Disjoint Paths in Bidirected Trees.	WAE	2000	DBLP DOI BibTeX RDF
34	Hrushikesha Mohanty, G. P. Bhattacharjee	A Distributed Algorithm for Edge-Disjoint Path Problem.	FSTTCS	1986	DBLP DOI BibTeX RDF
32	Jeongsoo Han	Network-Adaptive QoS Routing Using Local Information.	APNOMS	2006	DBLP DOI BibTeX RDF	Localized Adaptive QoS Routing, Exploration Bonus, Certainty Equivalency Approximation, Edge-disjoint multi-path, Reinforcement Learning, POMDP
32	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	The all-or-nothing multicommodity flow problem.	STOC	2004	DBLP DOI BibTeX RDF	all-or-nothing multicommodity flow, approximation algorithms, online algorithms, multicommodity flow, oblivious routing, edge disjoint paths
32	Qian-Ping Gu, Shietung Peng	Efficient Protocols for Permutation Routing on All-Optical Multistage Interconnection Networks.	ICPP	2000	DBLP DOI BibTeX RDF	WDM all-optical networks, routing algorithms, multistage interconnection networks, Permutation routing, edge-disjoint paths, BPC permutations
32	Yefim Dinitz, Tamar Eilam, Shlomo Moran, Shmuel Zaks	On the totalk-diameter of connection networks.	ISTCS	1997	DBLP DOI BibTeX RDF	k edge-disjoint paths, minimal sum of lengths, fault-tolerant routing problems, k-connected simple graph, total/sub k/-diameter, graph theory, lower bound, ATM networks, upper bound, nodes, compact routing, connection network
32	Torsten Tholey	Finding Disjoint Paths on Directed Acyclic Graphs.	WG	2005	DBLP DOI BibTeX RDF
30	Marwan Al-Jubeh, Michael Hoffmann 0001, Mashhood Ishaque, Diane L. Souvaine, Csaba D. Tóth	Convex Partitions with 2-Edge Connected Dual Graphs.	COCOON	2009	DBLP DOI BibTeX RDF
30	Lap Chi Lau	An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem*.	Comb.	2007	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C05, 68R10, 05C70, 68W25, 05C40
30	Lap Chi Lau	An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem.	FOCS	2004	DBLP DOI BibTeX RDF
30	Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman	Short length menger's theorem and reliable optical routing.	SPAA	2003	DBLP DOI BibTeX RDF	flow number, menger's theorem, fault-tolerant routing, path coloring
29	Joseph Cheriyan, Mohammad R. Salavatipour	Hardness and Approximation Results for Packing Steiner Trees.	Algorithmica	2006	DBLP DOI BibTeX RDF	Approximation algorithms, Steiner trees, Hardness of approximation, Packing problems
28	Lenwood S. Heath, John Paul C. Vergara	Edge-Packing in Planar Graphs.	Theory Comput. Syst.	1998	DBLP DOI BibTeX RDF
28	Adrian Kosowski	Approximation Strategies for Routing Edge Disjoint Paths in Complete Graphs.	SIROCCO	2006	DBLP DOI BibTeX RDF
28	Li Yang	Building k Edge-Disjoint Spanning Trees of Minimum Total Length for Isometric Data Embedding.	IEEE Trans. Pattern Anal. Mach. Intell.	2005	DBLP DOI BibTeX RDF	dimensionality reduction, minimum spanning tree, manifold learning, Data embedding, neighborhood graph
28	Chandra Chekuri, Sanjeev Khanna	Edge disjoint paths revisited.	SODA	2003	DBLP BibTeX RDF
28	Aleksandrs Slivkins	Parameterized Tractability of Edge-Disjoint Paths on Directed Acyclic Graphs.	ESA	2003	DBLP DOI BibTeX RDF
28	Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini 0001, Charis Papadopoulos, Frances A. Rosamond	Clustering with Partial Information.	MFCS	2008	DBLP DOI BibTeX RDF
28	Joseph Cheriyan, Adrian Vetta	Approximation algorithms for network design with metric costs.	STOC	2005	DBLP DOI BibTeX RDF	metric costs, approximation algorithms, graph connectivity
28	András Frank, Zoltán Király	Graph Orientations with Edge-connection and Parity Constraints.	Comb.	2002	DBLP DOI BibTeX RDF	AMS Subject Classification (2000) Classes: 05C75, 05C40
28	András Frank, Zoltán Király	Parity Constrained k-Edge-Connected Orientations.	IPCO	1999	DBLP DOI BibTeX RDF
27	Yi-Zhi Xu, Ho Fai Po, Chi Ho Yeung, David Saad	Scalable Node-Disjoint and Edge-Disjoint Multi-wavelength Routing.	CoRR	2021	DBLP BibTeX RDF
27	Zbigniew R. Bogdanowicz	Arc-Disjoint and Edge-Disjoint Hamilton Cycles in Circulants with Two Jumps.	Graphs Comb.	2013	DBLP DOI BibTeX RDF
27	Ruo-Wei Hung	Constructing Two Edge-Disjoint Hamiltonian Cycles and Two Equal Node-Disjoint Cycles in Twisted Cubes	CoRR	2010	DBLP BibTeX RDF
27	Robin W. Whitty	Vertex-disjoint paths and edge-disjoint branchings in directed graphs.	J. Graph Theory	1987	DBLP DOI BibTeX RDF
25	Koichi Wada 0001, Akinari Takaki, Kimio Kawaguchi	Efficient Algorithms for a Mixed k-Partition Problem of Graphs without Specifying Bases.	WG	1994	DBLP DOI BibTeX RDF
25	Markus Maier, Steffen Mecke, Dorothea Wagner	Algorithmic Aspects of Minimum Energy Edge-Disjoint Paths in Wireless Networks.	SOFSEM (1)	2007	DBLP DOI BibTeX RDF
25	Chuan-Ching Sue, Min-Shao Shieh, Chin-Yu Huang	Dependable WDM networks with reconfigurable edge-disjoint p-cycles.	ITRE	2005	DBLP DOI BibTeX RDF
25	Chuan-Ching Sue, Yung-Chiao Chen, Min-Shao Shieh, Sy-Yen Kuo	Dependable WDM Networks with Edge-Disjoint P-Cycles.	ISPA	2004	DBLP DOI BibTeX RDF
25	Luke Mathieson, Elena Prieto-Rodriguez, Peter Shaw 0001	Packing Edge Disjoint Triangles: A Parameterized View.	IWPEC	2004	DBLP DOI BibTeX RDF
25	Paz Carmi, Thomas Erlebach, Yoshio Okamoto	Greedy Edge-Disjoint Paths in Complete Graphs.	WG	2003	DBLP DOI BibTeX RDF	Shortening lemma, Approximation algorithm, Greedy algorithm
25	Myung Hee Kim, Hyunseung Choo, Byung Ho Yae, Jonghyun Lee	A Practical RWA Algorithm Based on Lookup Table for Edge Disjoint Paths.	Human.Society@Internet 2003	2003	DBLP DOI BibTeX RDF
25	Myung M. Bae, Bella Bose	Gray Codes for Torus and Edge Disjoint Hamiltonian Cycles.	IPDPS	2000	DBLP DOI BibTeX RDF
25	Karsten Weihe	Edge-Disjoint Routing in Plane Switch Graphs in Linear Time.	FOCS	1999	DBLP DOI BibTeX RDF	Graph algorithms, planar graphs, disjoint paths
25	Xiao Zhou 0001, Takao Nishizeki	The Edge-Disjoint Paths Problem is NP-Complete for Partial k-Trees.	ISAAC	1998	DBLP DOI BibTeX RDF
25	C. P. Gopalakrishnan, C. Pandu Rangan	Edge-Disjoint Paths in Permutation Graphs.	ISAAC	1994	DBLP DOI BibTeX RDF
25	Karsten Weihe	Edge-Disjoint (s, t)-Paths on Undirected Planar Graphs in Linear Time.	ESA	1994	DBLP DOI BibTeX RDF
25	Juraj Hromkovic, Ralf Klasing, Walter Unger, Hubert Wagener	Optimal Algorithms for Broadcast and Gossip in the Edge-Disjoint Path Modes (Extended Abstract).	SWAT	1994	DBLP DOI BibTeX RDF	parallel computations, communication algorithms
25	Dorothea Wagner, Karsten Weihe	A Linear-Time Algorithm for Edge-Disjoint Paths in Planar Graphs.	ESA	1993	DBLP DOI BibTeX RDF
25	H. Narayanan, Huzur Saran, Vijay V. Vazirani	Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arboresences and Edge-Disjoint Spanning Trees.	SODA	1992	DBLP BibTeX RDF
24	Egon Wanke, Rolf Kötter	Oriented Paths in Mixed Graphs.	ISAAC	2004	DBLP DOI BibTeX RDF
24	Noga Alon, Michael R. Capalbo	Finding Disjoint Paths in Expanders Deterministically and Online.	FOCS	2007	DBLP DOI BibTeX RDF
24	Lap Chi Lau	Packing Steiner Forests.	IPCO	2005	DBLP DOI BibTeX RDF
24	Joseph Cheriyan, Mohammad R. Salavatipour	Hardness and Approximation Results for Packing Steiner Trees.	ESA	2004	DBLP DOI BibTeX RDF
24	Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana	Polynomial-Time Algorithms for Minimum-Time Broadcast in Trees.	Theory Comput. Syst.	2002	DBLP DOI BibTeX RDF
24	Philippe Flajolet, Kostas P. Hatzis, Sotiris E. Nikoletseas, Paul G. Spirakis	Trade-Offs between Density and Robustness in Random Interconnection Graphs.	IFIP TCS	2000	DBLP DOI BibTeX RDF
24	Nihar R. Mahapatra, Shantanu Dutt	Efficient Network-Flow Based Techniques for Dynamic Fault Reconfiguration in FPGAs.	FTCS	1999	DBLP DOI BibTeX RDF
23	Ruen Chze Loh, Sieteng Soh, Mihai M. Lazarescu	Maximizing Bandwidth Using Disjoint Paths.	AINA	2010	DBLP DOI BibTeX RDF	maximum bandwidth, path bandwidth, edge-disjoint paths, network bandwidth, network QoS
23	Chi-Geun Han	Survivable Networks.	Encyclopedia of Optimization	2009	DBLP DOI BibTeX RDF	Local search, Network design, Survivability, Node-disjoint path, Edge-disjoint path
23	Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd	A Note on Multiflows and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Product multicommodity flow, Treewidth, Edge-disjoint paths
23	Ruen Chze Loh, Sieteng Soh, Mihai M. Lazarescu	An Approach to Find Maximal Disjoint Paths with Reliability and Delay Constraints.	AINA	2009	DBLP DOI BibTeX RDF	multi-constrained edge disjoint paths, approximate algorithm, network reliability, network delay, Lagrange relaxation
23	Bin Wang, Xiao-Min Li, Lan Lei	A Degree-Condition for ( s , t )-Supereulerian Graphs.	International Conference on Computational Science (3)	2007	DBLP DOI BibTeX RDF	(s, t)-supereulerian, Reduced Graph, Edge-disjoint Spanning Trees, Collapsible
23	Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar	Hardness of routing with congestion in directed graphs.	STOC	2007	DBLP DOI BibTeX RDF	all-or-nothing flow, hardness of approximation, multicommodity flow, edge-disjoint paths, integrality gap, congestion minimization
23	Stavros G. Kolliopoulos, Clifford Stein 0001	Approximating disjoint-path problems using packing integer programs.	Math. Program.	2004	DBLP DOI BibTeX RDF	packing integer programs, approximation algorithms, edge-disjoint paths
23	Hee Yong Youn, Jae Young Lee	An Efficient Dictionary Machine Using Hexagonal Processor Arrays.	IEEE Trans. Parallel Distributed Syst.	1996	DBLP DOI BibTeX RDF	edge disjoint embedding, update and query, processor array, hexagonal mesh, Dictionary machine
23	Emmanouel A. Varvarigos, Ayan Banerjee	Routing Schemes for Multiple Random Broadcasts in Arbitrary Network Topologies.	IEEE Trans. Parallel Distributed Syst.	1996	DBLP DOI BibTeX RDF	edge-disjoint trees, dynamic broadcasting, queuing systems, General graphs
23	Jenn-Yang Tien, Ching-Tien Ho, Wei-Pang Yang	Broadcasting on Incomplete Hypercubes.	IEEE Trans. Computers	1993	DBLP DOI BibTeX RDF	edge-disjoint spanning trees, delays, hypercube networks, trees (mathematics), broadcasting algorithm, incomplete hypercube, faulty nodes
23	Samir Khuller, Baruch Schieber	Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary)	FOCS	1989	DBLP DOI BibTeX RDF	k-edge disjoint paths, testing connectivity, disjoint s-t paths, optimal speedup algorithm, k-vertex connectivity, parallel algorithms, graphs, CRCW PRAM
22	Guy Kortsarz, Vahab S. Mirrokni, Zeev Nutov, Elena Tsanko	Approximating Minimum-Power Degree and Connectivity Problems.	LATIN	2008	DBLP DOI BibTeX RDF
22	Yefim Dinitz, Ronit Nossenson	Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph.	SWAT	2000	DBLP DOI BibTeX RDF