View source for ट्रीविड्थ

एक आलेख सिद्धांत में, [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष]] आलेख की '''ट्रीविड्थ''' एक [[पूर्णांक]] संख्या है, जो अनौपचारिक रूप से निर्दिष्ट करती है कि आलेख एक ट्री से कितनी दूर है। सबसे छोटी ट्रीविड्थ 1 है; और ट्रीविड्थ 1 वाले आलेख वास्तव में ट्री और फॉरेस्ट्स हैं। अधिकतम 2 ट्रीविड्थ वाले आलेख श्रृंखला-समानांतर आलेख हैं। यथार्थत: {{mvar|k}} ट्रीविड्थ वाले उच्चतम आलेख को k-ट्री कहा जाता है, और अधिकतर {{mvar|k}} पर ट्रीविड्थ वाले आलेख को आंशिक {{math|k}}-ट्री कहा जाता है। कई अन्य अच्छी तरह से अध्ययन किए गए आलेख श्रेणीयों में भी ट्रीविड्थ की सीमा होती है।

ट्रीविड्थ को औपचारिक रूप से कई समतुल्य माध्यमों से परिभाषित किया जा सकता है: आलेख के [[वृक्ष अपघटन|ट्री अपघटन]] में निर्धारित किए गए सबसे बड़े शीर्ष आकार, आलेख के पृष्ठ रज्जु समापन में सबसे बड़े गुट्ट के आकार, और हेवन के अधिकतम क्रम के संदर्भ में आलेख पर खोज-उत्सरण के खेल के लिए एक रणनीति का वर्णन, या एक कंटक गुल्म के अधिकतम क्रम के संदर्भ में, जुड़े उप-आलेख का एक संग्रह जो सम्पूर्ण एक दूसरे को स्पर्श करते हैं .

ट्रीविड्थ का उपयोग सामान्यतः आलेख [[कलन विधि]] के पैरामिट्रीकृत जटिलता विश्लेषण में एक मापदण्ड के रूप में किया जाता है। कई कलन विधि जो सामान्य आलेख के लिए [[ एनपी कठिन |एनपी अटल]] हैं, यह तब सरल आसान हो जाते हैं जब ट्रीविड्थ एक स्थिरांक से घिरा होता है। 

ट्रीविड्थ की अवधारणा मूल रूप अम्बर्टो बर्टेल और फ्रांसेस्को ब्रियोची (1972) द्वारा आयाम के नाम से प्रस्तुत की गई थी। इसे बाद में द्वारा पुनः {{harvs|last=हेलिन|first=रुडोल्फ|authorlink=रुडोल्फ हेलिन|year=1976|txt}} द्वारा खोजा गया था, उन गुणों के आधार पर जो इसे एक अलग आलेख मापदण्ड, [[हैडविगर संख्या]] के साथ साझा करते है। तत्पश्चात इसे पुनः नील रॉबर्टसन और पॉल सीमोर (1984) द्वारा खोजा गया था और उसके पश्चात कई अन्य लेखकों द्वारा इसका अध्ययन किया जा रहा है।<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>


== परिभाषा ==
[[Image:Tree decomposition.svg|thumb|240px|आठ शीर्षों वाले एक आलेख, और छह बिंदु वाले एक ट्री पर एक ट्री अपघटन है। प्रत्येक आलेख दो शीर्षों को जोड़ता है जो किसी ट्री बिंदु पर एक साथ सूचीबद्ध होते हैं, और प्रत्येक आलेख शीर्ष को ट्री के सन्निहित सबट्री के बिंदु पर सूचीबद्ध करते है। प्रत्येक ट्री बिंदु अधिकतम तीन शीर्षों को सूचीबद्ध करता है, इसलिए इस अपघटन की चौड़ाई दो है।]]एक आलेख {{math|1={{mvar|G}} = (''V'', ''E'')}} का ट्री अपघटन एक ट्री {{mvar|T}} है जिसमें बिंदु {{math|''X''{{sub|1}}, …, ''X''{{sub|''n''}}}}, जहां प्रत्येक {{mvar|X{{sub|i}}}} का एक उपसमुच्चय {{mvar|V}} है, जो निम्नलिखित गुणों को संतुष्ट करता हैː<ref>{{harvtxt|Diestel|2005}} section 12.3</ref> 
# सम्पूर्ण समुच्चयों का संघ {{mvar|X{{sub|i}}}} {{mvar|V}} के समान है, अर्थात, प्रत्येक आलेख शीर्ष कम से कम एक ट्री बिंदु में समाहित है।
# यदि {{mvar|X{{sub|i}}}} और {{mvar|X{{sub|j}}}} दोनों में एक शीर्ष {{mvar|v}} है, तो {{mvar|X{{sub|i}}}} और {{mvar|X{{sub|j}}}} के मध्य (अद्वितीय) पथ में {{mvar|T}} के सम्पूर्ण बिंदु {{mvar|X{{sub|k}}}} में {{mvar|v}} भी सम्मिलित है। समतुल्य रूप से, ट्री बिंदु में शीर्ष {{mvar|v}} होते है, और {{mvar|T}} के सम्बद्ध सबट्री का निर्माण किया जाता है।
# आलेख में प्रत्येक किनारो {{math|(''v'', ''w'')}} के लिए, एक उपसमुच्चय {{mvar|X{{sub|i}}}} है जिसमें {{mvar|v}} और {{mvar|w}} दोनों सम्मिलित हैं, अर्थात, शीर्ष आलेखों में आसन्न होते हैं, जब संबंधित सबट्री में एक सामान्य बिंदु होता है।
एक ट्री के अपघटन की चौड़ाई उसके सबसे बड़े समुच्चय {{mvar|X{{sub|i}}}} का आकार न्यूनतम है। एक आलेख {{mvar|G}} की ट्रीविड्थ {{math|tw(''G'')}} के सम्पूर्ण संभव ट्री अपघटन के मध्य न्यूनतम चौड़ाई {{mvar|G}} है। इस परिभाषा में, एक ट्री की ट्रीविड्थ को एक के समान बनाने के लिए सबसे बड़े समुच्चय का आकार एक से कम किया जाता है।

सामान्य रूप से, {{mvar|G}} की ट्रीविड्थ [[कॉर्डल ग्राफ|पृष्ठरज्जु आलेख]] में सबसे छोटे गुट्ट के आकार से एक कम है, जिसमें {{mvar|G}} सबसे छोटी गुट्ट संख्या है। इस गुट्ट के आकार के साथ एक पृष्ठरज्जु आलेख {{mvar|G}} को प्रत्येक दो शीर्षों के मध्य जोड़कर प्राप्त किया जा सकता है, जो दोनों समुच्चयों में से कम से कम एक समुच्चय {{mvar|X{{sub|i}}}} से संबंधित हैं।

ट्रीविड्थ को हेवन के संदर्भ में भी चित्रित किया जा सकता है, एक आलेख पर परिभाषित एक निश्चित खोज-उत्सरण के खेल के लिए एक उत्सरण की रणनीति का वर्णन करने वाले फलन हैं। एक आलेख {{mvar|G}} में ट्रीविड्थ {{mvar|k}} है, और यदि केवल उसके पास {{math|''k'' + 1}} क्रम है परन्तु कोई उच्च क्रम नहीं है, जहां क्रम  {{math|''k'' + 1}} का एक आश्रय  फलन {{mvar|β}} है जो प्रत्येक समुच्चय {{mvar|X}} को {{mvar|G}} में अधिकांश  {{mvar|k}} शीर्षों में प्रतिचित्र करता है, {{math|{{mvar|G}} \ ''X''}}  के जुड़े घटकों में से एक और जो एकरसता गुण का पालन करता है कि {{math|''&beta;''(''Y'') ⊆ ''&beta;''(''X'')}} जब भी {{math|''X'' ⊆ ''Y''}} हैं।

[[File:3x3 grid graph haven.svg|thumb|3×3 संजाल आलेख में क्रम चार का एक कंटक गुल्म (आलेख सिद्धांत), जिसके अस्तित्व से ज्ञात होता है कि आलेख में कम से कम 3 ट्रीविड्थ है]]एक समान लक्षण वर्णन कंटक-गुल्म का उपयोग करके भी किया जा सकता है, और जुड़े हुए उप-आलेख की श्रेणी जहां सभी एक दूसरे को स्पर्श करते हैं (अर्थात् या तो वे एक शीर्ष से साझा करते हैं या किनारे से जुड़े होते हैं)।<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref> एक कंटक-गुल्म का क्रम उप-आलेख के श्रेणी के लिए सबसे छोटा [[हिटिंग सेट|आघाती समुच्चय]] है, और आलेख की ट्रीविड्थ एक कंटक-गुल्म के अधिकतम क्रम से एक कम है।

== उदाहरण ==
प्रत्येक [[पूरा ग्राफ|पूर्ण आलेख]] {{mvar|K{{sub|n}}}} में ट्रीविड्थ{{math| ''n'' – 1}} है। पृष्ठरज्जु आलेख के संदर्भ में ट्रीविड्थ की परिभाषा का उपयोग करके इसे सरलता से देखा जा सकता है: सम्पूर्ण आलेख पहले से ही पृष्ठरज्जु है, और अधिक किनारों को जोड़ने से इसके सबसे बड़े समूह के आकार को कम नहीं किया जा सकता है।

कम से कम दो शीर्षों वाले संसक्त आलेख में ट्रीविड्थ 1 है, और यदि केवल वह एक ट्री है। एक ट्री की ट्रीविड्थ एक ही युक्ति के अनुसार पूर्ण रेखांकन के लिए होती है (अर्थात्, यह पृष्ठरज्जु है, और अधिकतम गुट्ट आकार दो है)। इसके विपरीत, यदि किसी आलेख में एक चक्र है, तो आलेख के प्रत्येक पृष्ठरज्जु पूर्णता में कम से कम एक त्रिभुज सम्मिलित होता है जिसमें चक्र के निरंतर तीन शीर्ष होते हैं, जिससे यह ज्ञात होता है कि इसकी ट्रीविड्थ कम से कम दो है।

== परिबद्ध ट्रीविड्थ ==

=== परिबद्ध ट्रीविड्थ वाले आलेख श्रेणी ===
किसी निश्चित स्थिरांक {{mvar|k}} के लिए,अधिकांश {{mvar|k}} पर ट्रीविड्थ के आलेख को आंशिक {{mvar|k}}-ट्री कहा जाता है। परिबद्ध ट्रीविड्थ वाले आलेख के अन्य श्रेणीयों में [[कैक्टस ग्राफ|कैक्टस]] आलेख, [[seudoforest|स्यूडोफॉरेस्ट]], श्रृंखला-समानांतर आलेख, बाहरी आलेख, [[हालीन ग्राफ|हालीन आलेख]] और [[अपोलोनियन नेटवर्क|अपोलोनियन संजाल]] सम्मिलित हैं।<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref> [[संरचित प्रोग्रामिंग|संरचित क्रमादेश]] के [[संकलक]] में उत्पन्न होने वाले [[नियंत्रण-प्रवाह ग्राफ|नियंत्रण-प्रवाह]] आलेख में भी ट्रीविड्थ की सीमा होती है, जो कुछ कार्यों जैसे कि पंजीकृत आवंटन को कुशलतापूर्वक निष्पादित करने की अनुमति देता है।<ref>{{harvtxt|Thorup|1998}}.</ref>

समतलीय आलेख में ट्रीविड्थ की सीमा नहीं होता है, क्योंकि {{math|''n'' × ''n''}} [[ग्रिड ग्राफ|संजाल आलेख]] ट्रीविड्थ के साथ एक समतलीय आलेख {{mvar|n}} है, इसलिए यदि {{mvar|F}} एक उपसारणिक-अवरुद्ध आलेख श्रेणी है जिसमें परिबद्ध ट्रीविड्थ है, तो इसमें सभी समतलीय आलेख सम्मिलित नहीं हो सकते। इसके विपरीत, यदि कुछ समतलीय आलेख श्रेणी {{mvar|F}} में आलेख के लिए उपसारणिको के रूप में नहीं हो सकते हैं, तो एक स्थिरांक {{mvar|k}} है, जैसे कि {{mvar|F}} में सभी आलेखों में अधिकतम {{mvar|k}} पर ट्रीविड्थ होती है, अर्थात्, निम्नलिखित तीन स्थितियाँ एक दूसरे के समतुल्य हैं:<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
#{{mvar|F}} परिबद्ध -ट्रीविड्थ आलेख की उपसारणिक-अवरुद्ध श्रेणी है;
# {{mvar|F}} की विशेषता वाले बहुत से निषिद्ध उपसारणिको में से एक समतलीय है;
#{{mvar|F}} एक उपसारणिक-अवरुद्ध आलेख श्रेणी है जिसमें सभी समतलीय आलेख सम्मिलित नहीं हैं

===निषिद्ध उपसारणिक===

[[File:Partial 3-tree forbidden minors.svg|thumb|300px|ट्रीविड्थ 3 के लिए चार प्रतिबंधित उपसारणिक: {{math|''K''{{sub|5}}}} (शीर्ष-बाएँ), अष्टफलक का आलेख (नीचे-बाएँ), वैगनर आलेख (शीर्ष-दाएँ), और पंचकोणीय वर्णक्रम का आलेख (नीचे-दाएँ) है।]]{{mvar|k}} के प्रत्येक परिमित मान के लिए, अधिकांश {{mvar|k}} पर ट्रीविड्थ के आलेख को निषिद्ध उपसारणिक के परिमित समुच्चय द्वारा चित्रित किया जा सकता है। (अर्थात, ट्रीविड्थ {{math|> ''k''}} के किसी भी आलेखों के समुच्चय में से एक आलेख उपसारणिक के रूप में  सम्मिलित है)। निषिद्ध उपसारणिक के इन समुच्चयों में से प्रत्येक में कम से कम एक समतलीय आलेख सम्मिलित होता है।
*{{math|1=''k'' = 1}} के लिए, अद्वितीय निषिद्ध उपसारणिक 3-शीर्ष [[चक्र ग्राफ|चक्र आलेख]] है।<ref name="b88">{{harvtxt|Bodlaender|1988}}.</ref>
*{{math|1=''k'' = 2}} के लिए, अद्वितीय निषिद्ध उपसारणिक 4-शीर्ष पूर्ण आलेख {{math|''K''{{sub|4}}}} है।<ref name="b88" />
*{{math|1=''k'' = 3}} के लिए, चार निषिद्ध उपसारणिक {{math|''K''{{sub|5}}}} हैं, [[अष्टफलक]] का आलेख, [[पंचकोणीय प्रिज्म|पंचकोणीय]] [[प्रिज्म ग्राफ|वर्णक्रम आलेख]] और [[वैगनर ग्राफ|वैगनर आलेख]] इनमें से दो [[बहुफलकीय ग्राफ|बहुफलकीय आलेख]] समतलीय हैं।<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
{{mvar|k}} के बड़े मानों के लिए, निषिद्ध उपसारणिक की संख्या कम से कम उतनी ही तीव्रता से बढ़ती है जितनी कि {{mvar|k}} के वर्गमूल की चरघातांकी होती है।{{sfnp|Ramachandramurthi|1997}} हालांकि, निषिद्ध उपसारणिक के आकार और संख्या पर ज्ञात ऊपरी सीमाएं इस निचली सीमा से बहुत अधिक हैं।{{sfnp|Lagergren|1993}}

== कलन विधि ==

=== ट्रीविड्थ की गणना ===
यह निर्धारित करने के लिए एनपी-पूर्ण है। किसी दिए गए आलेख {{mvar|G}} में किसी दिए गए चर {{mvar|k}} पर ट्रीविड्थ है या नहीं है।{{sfnp|Arnborg|Corneil|Proskurowski|1987}}

हालाँकि, जब {{mvar|k}} एक निश्चित स्थिरांक होता है, तो ट्रीविड्थ {{mvar|k}} वाले आलेख को पहचाना जा सकता है, और रैखिक समय में एक चौड़ाई {{mvar|k}} ट्री अपघटन का निर्माण किया जाता है।<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> {{mvar|k}} पर इस कलन विधि की समय निर्भरता चरघातांकी है।

एक बड़ी संख्या में क्षेत्रों में ट्रीविड्थ की भूमिकाओं के कारण, आलेख के ट्रीविड्थ की गणना करने वाले विभिन्न व्यावहारिक और सैद्धांतिक कलन विधि विकसित की गई थी। आवेदन के आधार पर, कोई उन्नत सन्निकटन अनुपात, या इनपुट के आकार या ट्रीविड्थ से चलने वाले समय में उन्नत निर्भरता पसंद कर सकता है। नीचे दी गई तालिका में कुछ ट्रीविड्थ की कलन विधि का अवलोकन किया गया है। जहाँ {{mvar|k}} ट्रीविड्थ है और {{mvar|n}} एक इनपुट आलेख {{mvar|G}} के शीर्षों की संख्या है।

प्रत्येक कलन विधि समय में  {{math|''f''(''k'') ⋅ ''g''(''n'')}} अनुमानित स्तम्भ में दी गई चौड़ाई का अपघटन करता है। उदाहरण  लिए, समय {{math|''2''{{sup|''O''(''k''{{sup|3}})}}⋅''n''}} में {{harvtxt|बोडलैंडर|1996}} की कलन विधि या तो अधिकतम {{mvar|k}} पर चौड़ाई के इनपुट आलेख {{mvar|G}} के ट्री अपघटन का निर्माण या विवरण करता है कि {{mvar|G}} की ट्रीविड्थ {{mvar|k}} से अधिक है। इसी प्रकार, बोडलैंडर एट अल (2016) समय {{math|2{{sup|''O''(''k'')}}⋅''n''}} में या तो अधिकतम {{math|5''k'' + 4}} चौड़ाई के इनपुट आलेख {{mvar|G}} के ट्री अपघटन का निर्माण या विवरण करता है कि {{mvar|G}} की ट्रीविड्थ {{mvar|k}} से अधिक है, {{harvtxt|कोरहोनेन|2021}}  ने समान संचालन समय में इसे सुधार कर {{math|2''k'' + 1}} कर दिया है।
{| class="wikitable"
|-
! सन्निकटन !! {{math|''f''(''k'')}} !! {{math|''g''(''n'')}} !! संदर्भ
|-
| यथार्थ || {{math|''O''(1)}} || {{math|''O''(''n''{{sup|''k''+2}})}} || {{harvtxt|अर्नबोर्ग|कॉर्नियल|प्रोस्कुरोव्स्की|1987}}
|-
|  {{math|4''k'' + 3}}  || {{math|''O''(3{{sup|3''k''}})}} || {{math|''O''(''n''{{sup|2}})}} || {{harvtxt|रॉबर्टसन|सेमुर|1995}}
|-
| {{math|8''k'' + 7}}|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log{{sup|2}} ''n''}} || {{harvtxt|लेगरग्रेन|1996}}
|-
| {{math|5''k'' + 4}} (or {{math|7''k'' + 6}})|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log ''n''}} || {{harvtxt|रीड|1996}}
|-
|  यथार्थ || {{math|2{{sup|''O''(''k''{{sup|3}})}}}} || {{math|''O''(''n'')}} ||{{harvtxt|बोडलैंडर|1996}}
|-
|  <math>O \left( k \cdot \sqrt{\log k} \right)</math> || {{math|''O''(1)}}|| {{math|''n''{{sup|''O''(1)}}}} ||{{harvtxt|फीज|हजियाघयी|ली|2008}}
|-
|  {{math|4.5''k'' + 4}} || {{math|2{{sup|3''k''}}}} || {{math|''n''{{sup|2}}}} ||{{harvtxt|आमिर|2010}}
|-
|  {{math|{{sfrac|11|3}}''k'' + 4}} || {{math|2{{sup|3.6982''k''}}}} || {{math|''n''{{sup|3}} log{{sup|4}}''n''}} ||{{harvtxt|आमिर |2010}}
|-
|  यथार्थ || {{math|''O''(1)}}|| {{math|''O''(1.7347{{sup|''n''}})}} || {{harvtxt|फोमिन|टोडिंका|विलंगेर|2015}}
|-
|  {{math|3''k'' + 2}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|बोडलैंडर|ड्रैंज|ड्रेगी|फोमिन|2016}}
|-
|  {{math|5''k'' + 4}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'')}} || {{harvtxt|बोडलैंडर|ड्रैंज|ड्रेगी|फोमिन|2016}}
|-
|  {{math|''k''{{sup|2}}}}  || {{math|''O''(''k''{{sup|7}})}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|फोमिन|लोकशतानोव|सौरभ|पिलिपजुक|2018}}
|-
|  {{math|5''k'' + 4}}  || {{math|2{{sup|8.765''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|बेलबासी|फ्यूरर|2021a}}
|-
|{{math|2''k'' + 1}}
|{{math|2{{sup|''O''(''k'')}}}}
|{{math|''O''(''n'')}}
|{{harvtxt|कोरहोनेन|2021}}
|-
|  {{math|5''k'' + 4}}  || {{math|2{{sup|6.755''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|बेलबासी|फ्यूरर|2021b}}
|-
|  यथार्थ  || {{math|2{{sup|''O''(''k''{{sup|2}})}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|कोरहोनेन|लोकशतानोव|2022}}
|-
|  {{math|(1+<math>\varepsilon</math>)''k''}}  || {{math|k{{sup|''O''(''k''/<math>\varepsilon</math>)}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|कोरहोनेन|लोकशतानोव|2022}}
|-
|}

यह ज्ञात नहीं है कि समतलीय आलेख की ट्रीविड्थ का निर्धारण एनपी-पूर्ण है, या क्या उनकी ट्रीविड्थ की गणना बहुपद समय में की जा सकती है।{{sfnp|Kao|2008}}

व्यवहार में, शोइखेत और गीजर (1997) की एक कलन विधि 100 तक के शीर्षों और 11 तक की ट्रीविड्थ के साथ आलेखों की ट्रीविड्थ निर्धारित कर सकती है, और इष्टतम ट्रेविड्थ के साथ इन आलेखों पर पृष्ठरज्जु पूर्णता का पता लगाया जा सकता है।

एक बड़े आलेख के लिए, कोई भी खोज-आधारित प्रविधि जैसे शाखा और परिबद्ध (BnB) का उपयोग किया जा सकता है और ट्रीविड्थ की गणना करने के लिए सर्वप्रथम खोज की जा सकती है।

ट्रीविड्थ की गणना के लिए प्रथम बीएनबी कलन विधि, जिसे क्विकबीबी कलन विधि भी कहा जाता है<ref>{{Cite web |title=विभव गोगटे|url=https://personal.utdallas.edu/~vibhav.gogate/quickbb.html |access-date=2022-11-27 |website=personal.utdallas.edu}}</ref>जिसे गोगेट और डेक्टर द्वारा प्रस्तावित किया गया था।<ref name=":0">{{Cite arXiv |last1=Gogate |first1=Vibhav |last2=Dechter |first2=Rina |date=2012-07-11 |title=ट्रीविड्थ के लिए एक पूर्ण एनीटाइम एल्गोरिथम|class=cs.DS |eprint=1207.4109 }}</ref> चूँकि किसी भी बीएनबी कलन विधि की गुणवत्ता उपयोग की जाने वाली निचली सीमा की गुणवत्ता पर अत्यधिक निर्भर करती है, गोगेट और डेक्टर<ref name=":0" /> ने ट्रीविड्थ पर एक निचली सीमा की गणना के लिए एक उपन्यास कलन विधि भी प्रस्तावित की, जिसे उपसारणिक-न्यूनतम-चौड़ाई कहते हैं।<ref name=":0" />एक उच्च स्तर पर, उपसारणिक-न्यूनतम-चौड़ाई कलन विधि के तथ्यों को जोड़ती है। एक आलेख की ट्रीविड्थ कभी भी इसकी न्यूनतम डिग्री से बड़ी नहीं होती है या ट्रीविड्थ पर कम सीमा उत्पन्न करने के लिए छोटी होती है। उपसारणिक-न्यूनतम-चौड़ाई कलन विधि बार-बार एक न्यूनतम डिग्री शीर्ष और उसके सहवासीयों में से एक के मध्य शीर्षो को अनुबंधित करके एक [[ग्राफ माइनर|आलेख उपसारणिक]] का निर्माण करती है, जब तक कि केवल एक शीर्ष नहीं रह जाता है। इन निर्मित उपसारणिक पर न्यूनतम डिग्री की अधिकतम सीमा आलेख के ट्रीविड्थ पर निचली सीमा होने की अधिपत्रित है।

डॉव और कोर्फ़<ref>{{Cite web |title=ट्रीविड्थ के लिए सर्वश्रेष्ठ-प्रथम खोज|url=https://www.aaai.org/Library/AAAI/2007/aaai07-182.php |access-date=2022-11-27 |website=www.aaai.org}}</ref> ने सर्वोत्तम-प्रथम खोज का उपयोग करके क्विकबीबी कलन विधि में सुधार किया, और कुछ आलेखों पर, यह सर्वोत्तम-प्रथम खोज कलन विधि क्विकबीबी की तुलना में तीव्रता का एक क्रम है।

=== लघु ट्रीविड्थ के आलेख पर अन्य समस्याओं का समाधान ===
1970 के दशक के प्रारंभ में, यह देखा गया कि आलेख पर परिभाषित संयोजी अनुकूलन समस्याओं की एक बड़ी श्रेणी को गैर क्रमिक [[गतिशील प्रोग्रामिंग|गतिशील क्रमादेश]] द्वारा कुशलतापूर्वक हल किया जा सकता है, जब तक कि आलेख में एक परिबद्ध आयाम है,{{sfnp|Bertelè|Brioschi|1972}} {{harvtxt|बोडलैंडर|1998}} द्वारा ट्रीविड्थ के समतुल्य अवलोकन किये गये एक मापदण्ड है। पश्चात, 1980 दशक के अंत में कई लेखकों ने स्वतंत्र रूप से अवलोकन किया<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref> कि कई कलन विधि समस्याएं जो एनपी-पूर्ण हैं। इन आलेखों के ट्री-अपघटन का उपयोग करते हुए, बाध्य ट्रीविड्थ के आलेख के लिए गतिशील क्रमादेश द्वारा कुशलतापूर्वक हल किया जा सकता है।

एक उदाहरण के रूप में, ट्रीविड्थ {{mvar|k}} के आलेख में रंजक की समस्या को आलेख के ट्री अपघटन पर एक गतिशील क्रमादेश कलन विधि का उपयोग करके हल किया जा सकता है। ट्री अपघटन के प्रत्येक समुच्चय के लिए, और रंग वर्गों में  {{mvar|X{{sub|i}}}} के शीर्षों के प्रत्येक विभाजन के लिए, कलन विधि निर्धारित की जाती है कि क्या रंग मान्य है और ट्री अपघटन में सम्पूर्ण संतति बिंदु तक बढ़ाया जा सकता है, उन बिन्दुओ पर संग्रहीत एक समान प्रकार की सूचना के संयोजन से गणना की गयी थी। परिणामी कलन विधि समय {{math|''O''(''k''<sup>''k''+''O''(1)</sup>''n'')}} में {{mvar|n}}-शीर्ष आलेख का एक इष्टतम रंग प्राप्त करता है, और एक समयबद्धता जो इस समस्या को निश्चित-मापदण्ड सरल बनाती है।

=== कौरसेल प्रमेय ===
{{main|कौरसेल की प्रमेय}}
समस्याओं की एक बड़ी श्रेणी के लिए, कक्षा से किसी समस्या को हल करने के लिए एक रैखिक समय कलन विधि का उपयोग किया जाता है, यदि एक ट्री-अपघटन निरंतर बाध्य ट्रीविड्थ के साथ प्रदान की जाती है। विशेष रूप से, कौरसेल की प्रमेय<ref>{{harvtxt|Courcelle|1990}}; {{harvtxt|Courcelle|1992}}</ref>में व्याख्या की गयी है कि यदि एक आलेख समस्या को एक अक द्वितीय-क्रम तर्क का उपयोग करते हुए आलेख के तर्क में व्यक्त किया जा सकता है, तो इसे परिबद्ध ट्रीविड्थ के साथ आलेख पर रैखिक समय में हल किया जा सकता है। [[मोनाडिक दूसरे क्रम का तर्क|एक अक द्वितीय-क्रम तर्क]] आलेख गुणों का वर्णन करने वाली एक भाषा है जो निम्नलिखित निर्माणों का उपयोग करती है:
* तर्क संचालन, जैसे <math> \wedge ,\vee ,\neg ,\Rightarrow </math>
* सदस्यता परीक्षण, जैसे {{math|''e'' ∈ ''E''}}, {{math|''v'' ∈ ''V''}}
* शीर्षों, किनारों, शीर्षों के समुच्चयों और/या किनारों के समुच्चयों पर परिमाणीकरण, जैसे {{math|∀''v'' ∈ ''V''}}, {{math|∃''e'' ∈ ''E''}}, {{math|∃''I'' ⊆ ''V''}}, {{math|∀''F'' ⊆ ''E''}}
* निकटता परीक्षण ({{mvar|u}} का समापन बिंदु {{mvar|e}} है), और कुछ विस्तारण जो अनुकूलीकरण जैसी चीज़ों की अनुमति देते हैं।

उदाहरण, आलेख के लिए तीनों रंगों की समस्या पर विचार करें। एक आलेख {{math|1=''G'' = (''V'', ''E'')}} के लिए, यह समस्या है कि क्या तीनों रंगों के प्रत्येक शीर्ष {{math|''v'' ∈ ''V''}}  को निर्दिष्ट करना संभव है, ताकि कोई भी दो आसन्न शीर्षों को एक ही रंग में निर्दिष्ट न किया जा सके। इस समस्या को एक अक द्वितीय-क्रम तर्क में निम्नानुसार व्यक्त किया जा सकता है:
:<math> \exists W_1 \subseteq V : \exists W_2 \subseteq V : \exists W_3 \subseteq V : \forall v \in V : (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge </math>
:<math> \forall v \in V : \forall w \in V : (v,w) \in E \Rightarrow (\neg (v \in W_1 \wedge w \in W_1) \wedge \neg (v \in W_2 \wedge w \in W_2) \wedge \neg (v \in W_3 \wedge w \in W_3))</math>,
जहाँ  {{math|''W''{{sub|1}}}}, {{math|''W''{{sub|2}}}}, {{math|''W''{{sub|3}}}} तीनों रंगों में से प्रत्येक शीर्षों के उपसमुच्चय का प्रतिनिधित्व करते हैं।

इसलिए, कौरसेल के परिणामों से, 3-रंगों की समस्या को एक आलेख के लिए रैखिक समय में हल किया जा सकता है, जो कि परिबद्ध स्थिर ट्रीविड्थ का ट्री-अपघटन हैं।

== संबंधित मापदण्ड ==

===[[ पथचौड़ाई |पाथविड्थ]]===
एक आलेख के पाथविड्थ ट्री अपघटन के माध्यम से ट्रीविड्थ की एक बहुत ही समान परिभाषा है, लेकिन यह ट्री अपघटन तक ही सीमित है जिसमें अपघटन का अंतर्निहित ट्री एक [[पथ ग्राफ|पथ आलेख]] है। वैकल्पिक रूप से, पाथविड्थ को पृष्ठरज्जु आलेख से ट्रीविड्थ की परिभाषा के अनुरूप [[अंतराल ग्राफ|अंतराल]] आलेख से परिभाषित किया जा सकता है। परिणामस्वरूप, एक आलेख की पाथविड्थ सदैव कम से कम उतनी ही बड़ी होती है, जितनी इसकी ट्रीविड्थ होती है, लेकिन यह केवल एक उपसारणिक गणक कारक द्वारा बड़ी हो सकती है।<ref name="b98"/>एक अन्य मापदण्ड, [[ग्राफ बैंडविड्थ|आलेख बैंडविड्थ]], के [[उचित अंतराल ग्राफ|उचित अंतराल]] आलेख से समान परिभाषित है, और कम से कम पाथविड्थ जितना बड़ा है। अन्य संबंधित मापदंडों में [[ पेड़ की गहराई |ट्री गहनता]] सम्मिलित है, एक संख्या जो उपसारणिक-अवरुद्ध आलेख श्रेणी के लिए बाध्य है और यदि केवल श्रेणी एक पथ को बाहर करती है, और अध: पतन, एक आलेख की विरलता का एक उपाय जो ट्रीविड्थ के समान है।

===संजाल उपसारणिक आकार===
क्योंकि एक {{math|''n'' × ''n''}} संजाल आलेख की ट्रीविड्थ {{mvar|n}} है, आलेख {{mvar|G}} की ट्रीविड्थ सदैव {{mvar|G}} के सबसे बड़े श्रेणी संजाल आलेख के आकार से बड़ी या उसके बराबर होती है। दूसरी दिशा में, [[नील रॉबर्टसन (गणितज्ञ)|नील रॉबर्टसन]] और पॉल सीमोर के द्वारा संजाल उपसारणिक की प्रमेय को दर्शाया जाता है कि एक असीमित फलन  {{mvar|f}}  उपस्थित है जैसे कि सबसे बड़े वर्ग संजाल उपसारणिक का आकार कम से कम  {{math|''f''(''r'')}} है जहां {{mvar|r}} ट्रीविड्थ है।<ref>Robertson, Seymour. ''Graph minors. V. Excluding a planar graph''. [http://www.sciencedirect.com/science/article/pii/0095895686900304] {{Open access}}</ref>  {{mvar|f}}  पर ज्ञात सर्वोत्तम सीमाएँ हैं कि और कुछ निश्चित स्थिरांक {{math|''d'' > 0}} के लिए,  {{mvar|f}}  को कम से कम  {{math|Ω(''r''<sup>''d''</sup>)}} होना चाहिए।<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}</ref>
:<math>O \left( \sqrt{ r / \log r} \right).</math>
निचले परिबद्ध में {{math|Ω}} संकेतन के लिए , [[बिग ओ नोटेशन|बिग ओ संकेतन]] देखें। प्रतिबंधित आलेख श्रेणीयों के लिए घनिष्ठ सीमाएँ हैं, जिससे द्विविमता के सिद्धांत के माध्यम से श्रेणीयों पर कई आलेख अनुकूलन समस्याओं के लिए कुशल कलन विधि की ओर अग्रसर करता है।{{sfnp|Demaine|Hajiaghayi|2008}}

हैलिन की संजाल प्रमेय अनंत आलेख के लिए ट्रीविड्थ और संजाल उपसारणिक आकार के मध्य संबंध का एक तुल्यरूप प्रदान करती है।{{sfnp|Diestel|2004}}

=== व्यास और स्थानीय ट्रीविड्थ ===
एक उप-आलेख के अंतर्गत अवरुद्ध किए गए आलेख की एक श्रेणी को कहा जाता है कि स्थानीय ट्रीविड्थ, या व्यास-ट्रीविड्थ गुण से घिरा हुआ है, यदि श्रेणी में आलेख की ट्रीविड्थ उनके व्यास के एक फलन द्वारा ऊपरी सीमाबद्ध है। यदि आलेख उपसारणिको के अंतर्गत कक्षा को भी अवरुद्ध माना जाता है, तो {{mvar|F}} ने स्थानीय ट्रीविड्थ को बाध्य कर देता है और यदि केवल {{mvar|F}} के लिए निषिद्ध उपसारणिको में से एक [[शीर्ष ग्राफ|शीर्ष आलेख]] है।{{sfnp|Eppstein|2000}} इस परिणाम के मूल प्रमाणों से ज्ञात होता है कि शीर्ष-उपसारणिक-मुक्त आलेख श्रेणी में ट्रीविड्थ व्यास के फलन के रूप में सबसे अधिक दोगुनी घातीय रूप से बढ़ती है;<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004a}}.</ref> पश्चात इसे एकल घातांक {{sfnp|Demaine|Hajiaghayi|2008}} और अंत में एक रैखिक सीमा तक कम कर दिया जाता है।{{sfnp|Demaine|Hajiaghayi|2004b}}

परिबद्ध स्थानीय ट्रीविड्थ द्विविमीयता के कलन विधि सिद्धांत निकटता से संबंधित है,<ref>{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2004}}; {{harvtxt|Demaine|Hajiaghayi|2008}}.</ref> और प्रथम क्रम तर्क में परिभाषित प्रत्येक आलेख संपत्ति को शीर्ष-उपसारणिक-मुक्त आलेख श्रेणी के लिए तय किया जा सकता है जो कि केवल थोड़ा सुपरलाइनर है।{{sfnp|Frick|Grohe|2001}}

आलेख के एक श्रेणी के लिए यह भी संभव है कि स्थानीय ट्रीविड्थ को सीमित करने के लिए उपसारणिको के अंतर्गत अवरुद्ध नहीं किया जाता है। विशेष रूप से यह परिबद्ध डिग्री आलेख के एक श्रेणी के लिए नगण्यतापूर्वक सही है, क्योंकि परिबद्ध व्यास उप-आलेख में परिबद्ध के आकार होता है। एक अन्य उदाहरण [[1-प्लानर ग्राफ|1- समतली]] आलेख द्वारा दिया गया है कि आलेख जो प्रत्येक किनारो पर पारण के साथ समतलीय में खींचे जा सकते हैं, और अधिक सामान्यतः उन आलेखों के लिए होते हैं जो बंधे हुए वर्ग की सतह पर प्रत्येक किनारो पर पारण की एक सीमित संख्या के साथ खींचे जा सकते हैं। बंधे हुए स्थानीय ट्रीविड्थ के लघु-अवरुद्ध आलेख श्रेणीयों के साथ, इन आलेखों के लिए कुशल सन्निकटन कलन विधि की प्रणाली बताई गई है।{{sfnp|Grigoriev|Bodlaender|2007}}

=== हैडविगर संख्या और एस-फलन ===
{{harvtxt|हैलिन|1976}} आलेख मापदण्ड के एक श्रेणी को परिभाषित करता है जिसे {{mvar|S}}-फलन कहा जाता है, जिसमें ट्रीविड्थ सम्मिलित है। आलेख से लेकर पूर्णांक तक के कार्यों को बिना किनारों वाले आलेख पर शून्य होना आवश्यक है, लघु-एकदिष्ट होने के लिए (फलन  {{mvar|f}} को "लघु-एकदिष्ट" के रूप में संदर्भित किया जाता है यदि, जब भी {{mvar|H}},  {{mvar|G}} का उपसारणिक हो, तो एक के पास किसी के पास {{math|''f''(''H'') ≤ ''f''(''G'')}} होता है), और जब एक नया शीर्ष जोड़ा जाता है जो पिछले सम्पूर्ण शीर्षों के निकट होता है, और एक गुट्ट [[ वर्टेक्स विभाजक |विभाजक]] के दोनों ओर दो उप-आलेख से बड़ा मान लेने के लिए है। इस तरह के सम्पूर्ण कार्यों का समुच्चय तत्ववार न्यूनीकरण और अधिकतमकरण के संचालन के अंतर्गत एक [[पूर्ण जाली|सम्पूर्ण जालक]] बनाता है। इस जालक में शीर्ष तत्व ट्रीविड्थ है, और नीचे का तत्व हैडविगर संख्या है, जो दिए गए आलेख में सबसे बड़े पूर्ण उपसारणिक का आकार है।

==टिप्पणियाँ==
{{reflist|30em}}


==संदर्भ==
{{refbegin|30em}}
*{{citation
 | last = Amir | first = Eyal
 | doi = 10.1007/s00453-008-9180-4
 | issue = 4
 | journal = [[Algorithmica]]
 | mr = 2581059
 | pages = 448–479
 | title = Approximation algorithms for treewidth
 | volume = 56
 | year = 2010| s2cid = 5874913
 }}.
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Corneil | first2 = D. | author2-link = Derek Corneil
 | last3 = Proskurowski | first3 = A.
 | title = Complexity of finding embeddings in a {{nowrap|<math>k</math>-tree}}
 | journal = [[SIAM Journal on Matrix Analysis and Applications]]
 | volume = 8 | issue = 2 | year = 1987 | pages = 277–284 | doi = 10.1137/0608024}}.
*{{citation
 | last1 = Arnborg | first1 = Stefan
 | last2 = Proskurowski | first2 = Andrzej
 | last3 = Corneil | first3 = Derek G. | author3-link = Derek Corneil
 | doi = 10.1016/0012-365X(90)90292-P
 | issue = 1
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 1045920
 | pages = 1–19
 | title = Forbidden minors characterization of partial 3-trees
 | volume = 80
 | year = 1990| doi-access = free
 }}.
*{{citation
 | last1 = Arnborg | first1 = S.
 | last2 = Proskurowski | first2 = A.
 | title = Linear time algorithms for NP-hard problems restricted to partial {{nowrap|<math>k</math>-trees}}
 | journal = [[Discrete Applied Mathematics]]
 | volume = 23 | issue = 1 | year = 1989 | pages = 11–24 | doi = 10.1016/0166-218X(89)90031-0| doi-access = free }}.
*{{citation
 | last1 = Belbasi | first1 = Mahdi
 | last2 = Fürer | first2 = Martin
 | editor1-last = Uehara | editor1-first = Ryuhei
 | editor2-last = Hong | editor2-first = Seok-Hee | editor2-link = Seok-Hee Hong
 | editor3-last = Nandy | editor3-first = Subhas C.
 | arxiv = 2010.03105
 | contribution = An improvement of Reed's treewidth approximation
 | doi = 10.1007/978-3-030-68211-8_14
 | mr = 4239527
 | pages = 166–181
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = WALCOM: Algorithms and Computation – 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings
 | volume = 12635
 | year = 2021a| s2cid = 222177100
 }}.
*{{citation
 | last1 = Belbasi | first1 = Mahdi
 | last2 = Fürer | first2 = Martin
 | editor1-last = Du | editor1-first = Ding-Zhu
 | editor2-last = Du | editor2-first = Donglei
 | editor3-last = Wu | editor3-first = Chenchen
 | editor4-last = Xu | editor4-first = Dachuan
 | arxiv = 2111.02614
 | contribution = Finding all leftmost separators of size <math>\le k</math>
 | doi = 10.1007/978-3-030-92681-6_23
 | pages = 273–287
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings
 | volume = 13135
 | year = 2021b| s2cid = 242758210
 }}
*{{citation
 | last1 = Bern | first1 = M. W.
 | last2 = Lawler | first2 = E. L. | author2-link = Eugene Lawler
 | last3 = Wong | first3 = A. L.
 | title = Linear-time computation of optimal subgraphs of decomposable graphs
 | journal = Journal of Algorithms
 | volume = 8 | issue = 2 | year = 1987 | pages = 216–235 | doi = 10.1016/0196-6774(87)90039-3}}.
*{{citation
 | last1 = Bertelè | first1 = Umberto
 | last2 = Brioschi | first2 = Francesco
 | title = Nonserial Dynamic Programming
 | year = 1972
 | publisher = Academic Press
 | isbn = 978-0-12-093450-8
 | pages = 37–38
 | url = https://books.google.com/books?id=baw3LMwm-y8C&pg=PA37}}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | contribution = Dynamic programming on graphs with bounded treewidth
 | title = Proc. 15th International Colloquium on Automata, Languages and Programming
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 317 | year = 1988 | pages = 105–118
 | doi = 10.1007/3-540-19488-6_110| citeseerx = 10.1.1.18.8503| isbn = 978-3-540-19488-0 }}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | title = A linear time algorithm for finding tree-decompositions of small treewidth
 | journal = [[SIAM Journal on Computing]]
 | volume = 25 | issue = 6 | year = 1996 | pages = 1305–1317 | doi = 10.1137/S0097539793251219| citeseerx = 10.1.1.19.7484}}.
*{{citation
 | last = Bodlaender | first = Hans L. | author-link = Hans L. Bodlaender
 | title = A partial ''k''-arboretum of graphs with bounded treewidth
 | journal = Theoretical Computer Science
 | volume = 209 | issue = 1–2 | pages = 1–45 | year = 1998 | doi = 10.1016/S0304-3975(97)00228-4 | doi-access=free}}.
*{{citation
 | last1 = Bodlaender| first1 = Hans L.
 | last2 = Drange| first2 = Pal G.  
 | last3 = Dregi| first3 = Markus S.
 | last4 = Fomin| first4 = Fedor V.
 | last5 = Lokshtanov| first5 = Daniel
 | last6 = Pilipczuk| first6 = Michal
 | title = A <math>c^k n</math> 5-approximation algorithm for treewidth
 | journal = [[SIAM Journal on Computing]]
 | volume = 45
 | issue = 2 
 | year = 2016 
 | pages = 317–378 
 | doi = 10.1137/130947374| arxiv = 1304.6321}}.
*{{citation
 | last1 = Chekuri | first1 = Chandra
 | last2 = Chuzhoy | first2 = Julia | author2-link = Julia Chuzhoy
 | arxiv=1305.6577
 | doi = 10.1145/2820609
 | issue = 5
 | journal = [[Journal of the ACM]]
 | mr = 3593966
 | pages = A40:1–65
 | title = Polynomial bounds for the grid-minor theorem
 | volume = 63
 | year = 2016| s2cid = 209860422
 }}.
*{{citation|title = The monadic second-order logic of graphs I: Recognizable sets of finite graphs|last = Courcelle|first = B.|date = 1990|journal = [[Information and Computation]]|doi = 10.1016/0890-5401(90)90043-h|volume = 85|pages = 12–75|citeseerx = 10.1.1.158.5595}}.
*{{citation|title = The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.|last = Courcelle|first = B.|date = 1992|journal = Informatique Théorique|pages = 257–286|issue = 26}}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Fomin | first2 = Fedor V.
 | last3 = Hajiaghayi | first3 = MohammadTaghi
 | last4 = Thilikos | first4 = Dimitrios M.
 | year = 2004
 | doi = 10.1137/S0895480103433410
 | issue = 3
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2134412
 | pages = 501–511
 | title = Bidimensional parameters and local treewidth
 | volume = 18| citeseerx = 10.1.1.107.6195| s2cid = 7803025 }}.
*{{citation
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | doi = 10.1007/s00453-004-1106-1
 | issue = 3
 | journal = [[Algorithmica]]
 | mr = 2080518
 | pages = 211–215
 | title = Diameter and treewidth in minor-closed graph families, revisited
 | volume = 40
 | year = 2004a| s2cid = 390856 }}.
*{{citation
 | last1 = Demaine | first1 = Erik D.
 | last2 = Hajiaghayi | first2 = MohammadTaghi
 | contribution = Equivalence of local treewidth and linear local treewidth and its algorithmic applications
 | location = New York
 | mr = 2290974
 | pages = 840–849
 | publisher = ACM
 | title = Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 | year = 2004b}}.
*{{citation
 | last1 = Demaine| first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hajiaghayi| first2 = MohammadTaghi 
 | doi = 10.1007/s00493-008-2140-4
 | issue = 1
 | journal = [[Combinatorica]]
 | pages = 19–36
 | title = Linearity of grid minors in treewidth with applications through bidimensionality
 | url = http://erikdemaine.org/papers/GridMinors_Combinatorica/paper.pdf
 | volume = 28
 | year = 2008| s2cid = 16520181 }}.
*{{citation
 | last = Diestel | first = Reinhard
 | doi = 10.1007/BF02941538
 | journal = Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg
 | mr = 2112834
 | pages = 237–242
 | title = A short proof of Halin's grid theorem
 | volume = 74
 | year = 2004| s2cid = 124603912
 }}.
*{{Citation
| last=Diestel | first=Reinhard
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=978-3-540-26182-7
| url=http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
}}.
*{{citation
 | last = Eppstein | first = D. | author-link = David Eppstein
 | doi = 10.1007/s004530010020
 | issue = 3–4
 | journal = [[Algorithmica]]
 | mr = 1759751
 | pages = 275–291
 | title = Diameter and treewidth in minor-closed graph families
 | volume = 27
 | year = 2000| arxiv = math/9907126| s2cid = 3172160 }}.
*{{citation
 | last1 = Feige | first1 = Uriel
 | last2 = Hajiaghayi | first2 = MohammadTaghi 
 | last3 = Lee| first3 = James R.
 | title = Improved approximation algorithms for minimum weight vertex separators
 | journal = [[SIAM Journal on Computing]]
 | volume = 38 | issue = 2 | year = 2008 | pages = 629–657 | doi = 10.1137/05064299X| citeseerx = 10.1.1.597.5634}}.
*{{citation
 | last1 = Fomin | first1 = Fedor V. | author1-link = Fedor Fomin
 | last2 = Todinca | first2 = Ioan
 | last3 = Villanger | first3 = Yngve
 | doi = 10.1137/140964801
 | issue = 1
 | journal = [[SIAM Journal on Computing]]
 | pages = 54–87
 | title = Large induced subgraphs via triangulations and CMSO
 | volume = 44
 | year = 2015| arxiv = 1309.1559
 | s2cid = 15880453 }}.
*{{citation
 | last1 = Frick | first1 = Markus
 | last2 = Grohe | first2 = Martin | author2-link = Martin Grohe
 | doi = 10.1145/504794.504798
 | issue = 6
 | journal = [[Journal of the ACM]]
 | mr = 2143836
 | pages = 1184–1206
 | title = Deciding first-order properties of locally tree-decomposable structures
 | volume = 48
 | year = 2001| arxiv = cs/0004007
 | s2cid = 999472
 }}.
*{{citation
 | last1 = Fomin| first1 = Fedor V.
 | last2 = Lokshtanov| first2 = Daniel
 | last3 = Saurabh| first3 = Saket
 | last4 = Pilipczuk| first4 = Michal
 | last5 = Wrochna| first5 = Marcin
 | title = Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
 | journal = ACM Transactions on Algorithms
 | volume = 14
 | issue = 3 
 | year = 2018 
 | pages = 34:1–34:45 
 | doi = 10.1145/3186898| arxiv = 1511.01379| s2cid = 2144798
 }}.
*{{citation
 | last1 = Grigoriev | first1 = Alexander
 | last2 = Bodlaender | first2 = Hans L. | author2-link = Hans L. Bodlaender
 | doi = 10.1007/s00453-007-0010-x
 | issue = 1
 | journal = [[Algorithmica]]
 | mr = 2344391
 | pages = 1–11
 | title = Algorithms for graphs embeddable with few crossings per edge
 | volume = 49
 | year = 2007| citeseerx = 10.1.1.65.5071| s2cid = 8174422
 }}.
*{{Citation
 | title = ''S''-functions for graphs
 | year = 1976
 | last = Halin | first = Rudolf | author-link = Rudolf Halin
 | journal = Journal of Geometry
 | pages = 171–186
 | volume = 8
 | issue = 1–2
 | doi=10.1007/BF01917434
| s2cid = 120256194
 }}.
*{{citation|title=	Encyclopedia of Algorithms|editor-first=Ming-Yang|editor-last=Kao|publisher=Springer|year=2008|isbn=9780387307701|contribution=Treewidth of graphs|page=969|url=https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA969|quote=Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.}}
*{{citation
 | last = Korhonen | first = Tuukka
 | contribution = A Single-Exponential Time 2-Approximation Algorithm for Treewidth
 | doi = 10.1109/FOCS52979.2021.00026
 | pages = 184–192
 | publisher = IEEE
 | title = Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science
 | arxiv = 2104.07463
 | year = 2021| s2cid = 233240958
 }}.
*{{citation
 | last = Lagergren | first = Jens
 | contribution = An upper bound on the size of an obstruction
 | doi = 10.1090/conm/147/01202
 | location = Providence, RI
 | mr = 1224734
 | pages = 601–621
 | publisher = American Mathematical Society
 | series = Contemporary Mathematics
 | title = Graph structure theory (Seattle, WA, 1991)
 | volume = 147
 | year = 1993| isbn = 9780821851609
 }}.
*{{citation
 | last = Lagergren | first = Jens
 | doi = 10.1006/jagm.1996.0002
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 1368716
 | pages = 20–44
 | title = Efficient parallel algorithms for graphs of bounded tree-width
 | volume = 20
 | year = 1996}}.
*{{citation
 | last = Ramachandramurthi | first = Siddharthan
 | doi = 10.1137/S0895480195280010
 | issue = 1
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 1430552
 | pages = 146–157
 | title = The structure and number of obstructions to treewidth
 | volume = 10
 | year = 1997}}.
*{{citation
 | last = Reed | first = Bruce A. | author-link = Bruce Reed (mathematician)
 | editor1-last = Kosaraju | editor1-first = S. Rao
 | editor2-last = Fellows | editor2-first = Mike
 | editor3-last = Wigderson | editor3-first = Avi
 | editor4-last = Ellis | editor4-first = John A.
 | contribution = Finding approximate separators and computing tree width quickly
 | doi = 10.1145/129712.129734
 | pages = 221–228
 | publisher = ACM
 | title = Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada
 | year = 1992| s2cid = 16259988 }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph minors III: Planar tree-width
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 36
 | issue = 1 | year = 1984 | pages = 49–64
 | doi = 10.1016/0095-8956(84)90013-3| doi-access = free}}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph minors V: Excluding a planar graph
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 41 | issue = 1 | year = 1986 | pages = 92–114 | doi = 10.1016/0095-8956(86)90030-4| doi-access = free }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author-link1 = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul D. | author-link2 = Paul Seymour (mathematician)
 | title = Graph Minors XIII: The Disjoint Paths Problem
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 63 | issue = 1 | year = 1995 | pages = 65–110 | doi = 10.1006/jctb.1995.1006| doi-access = free }}.
*{{citation
 | last1 = Robertson | first1 = Neil | author1-link = Neil Robertson (mathematician)
 | last2 = Seymour | first2 = Paul | author2-link = Paul Seymour (mathematician)
 | last3 = Thomas | first3 = Robin | author3-link = Robin Thomas (mathematician)
 | doi = 10.1006/jctb.1994.1073
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]] | series = Series B
 | mr = 1305057
 | pages = 323–348
 | title = Quickly excluding a planar graph
 | volume = 62
 | year = 1994| doi-access = free
 }}.
*{{citation
 | last1 = Satyanarayana | first1 = A.
 | last2 = Tung | first2 = L.
 | doi = 10.1002/net.3230200304
 | issue = 3
 | journal = Networks
 | mr = 1050503
 | pages = 299–322
 | title = A characterization of partial 3-trees
 | volume = 20
 | year = 1990}}.
*{{citation
 | last1 = Seymour | first1 = Paul D. | author-link1 = Paul Seymour (mathematician)
 | last2 = Thomas | first2 = Robin | author2-link=Robin Thomas (mathematician)
 | title = Graph searching and a min-max theorem for tree-width
 | journal = [[Journal of Combinatorial Theory]] | series=Series B
 | volume = 58 | issue = 1 | pages = 22–33 | doi = 10.1006/jctb.1993.1027
 | year = 1993| doi-access = free }}.
*{{citation
 | last1 = Shoikhet | first1 = Kirill
 | last2 = Geiger | first2 = Dan
 | editor1-last = Kuipers | editor1-first = Benjamin
 | editor2-last = Webber | editor2-first = Bonnie L.
 | contribution = A Practical Algorithm for Finding Optimal Triangulations
 | contribution-url = https://www.aaai.org/Library/AAAI/1997/aaai97-029.php
 | pages = 185–190
 | publisher = AAAI Press / The MIT Press
 | title = Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Providence, Rhode Island, USA
 | year = 1997}}.
*{{citation
 | last = Thorup | first = Mikkel | author-link = Mikkel Thorup
 | title = All structured programs have small tree width and good register allocation
 | journal = [[Information and Computation]]
 | volume = 142 | issue = 2 | year = 1998 | pages = 159–181 | doi = 10.1006/inco.1997.2697| doi-access = free }}.
*{{cite arXiv
 | last1 = Korhonen | first1 = Tuukka
 | last2 = Lokshtanov | first2 = Daniel
 | title = An Improved Parameterized Algorithm for Treewidth
 | eprint = 2211.07154
 | year = 2022
 | class = cs.DS
 | mode=cs2}}.

{{refend}}

[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 28/02/2023]]
[[Category:Harv and Sfn no-target errors]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]