Vi anser att följande problem är största möjliga osammanhängande (MDPP). Vi får ett stort nätverk, och par av noder som vill kommunicera över vägar genom nätverket - målet är att samtidigt ansluta så många av dessa par som möjligt på ett sådant sätt att inga två kommunikationsvägar delar en kant i nätverket. Detta klassiska problem har nyligen kommit i fokus i dokument som diskuterar tillämpningar för routing i höghastighetsnät, där den nuvarande bristen på förståelse för MDPP är ett hinder för utformningen av praktiska heuristik. Vi betraktar klassen av tätt inbäddade, nästan euleriska grafer, som omfattar de tvådimensionella maskorna och andra planar och lokalt planara sammanlänkningsnät. Vi får en konstant-faktor approximationsalgoritm för maximal dishead ways problem för denna klass av grafer; detta förbättrar på en O(1og n)- approximation för specialfallet av den tvådimensionella mesh på grund av Aumann-Rabani och författarna. För nätverk som inte uttryckligen behöver vara "hög kapacitet", är detta den första approximationen av konstantfaktorn för MDPP i någon annan kategori av grafer än träd. Vi anser också att MDPP i on-line-inställningen, relevant "till applikationer där anslutning begär anive över tid och måste behandlas omedelbart. Här får vi en asymptotiskt optimal O(1og n)-kompetitiv on-line algoritm för samma klass av grafer; detta förbättrar på en O(1og n log n)-kompetitiv algoritm för specialfallet av mesh på grund av Awerbuch, Gawlick, Leighton och Rabani.
Kleinberg och Tardos ger i REF en approximationsalgoritm med konstant faktor för MaxEDP i grafer de kallar tätt inbäddade och nästan euleriska, och som generaliserar de rektilinjära rutnäten.
Disjoint paths in densely embedded graphs
{'venue': 'Proceedings of IEEE 36th Annual Foundations of Computer Science', 'journal': 'Proceedings of IEEE 36th Annual Foundations of Computer Science', 'mag_field_of_study': ['Computer Science']}