Rank-width
র্যাঙ্ক-প্রস্থ একটি গ্রাফ প্রস্থ পরামিতি যা গ্রাফ তত্ত্ব এবং প্যারামিটারাইজড জটিলতায় ব্যবহৃত হয় এবং রৈখিক বীজগণিত ব্যবহার করে সংজ্ঞায়িত করা হয়। এটি একটি প্রদত্ত গ্রাফের শীর্ষগুলির শ্রেণিবদ্ধ গুচ্ছ থেকে সংজ্ঞায়িত করা হয়, যা তাদের পাতার মতো শীর্ষযুক্ত ত্রিভুজ গাছ হিসাবে কল্পনা করা যেতে পারে। এই ধরনের গাছ থেকে যে কোনও প্রান্ত সরিয়ে ফেললে এটি দুটি সাবট্রিতে বিচ্ছিন্ন হয়ে যায় এবং শীর্ষগুলিকে দুটি সাবসেটে বিভক্ত করে। বিভাজনের এক পাশ থেকে অন্য দিকে অতিক্রম করা গ্রাফের প্রান্তগুলি একটি বায়াজ্যাসেন্সি ম্যাট্রিক্স দ্বারা বর্ণনা করা যেতে পারে; র্যাঙ্ক-প্রস্থের উদ্দেশ্যে, এই ম্যাট্রিক্সটি বাস্তব সংখ্যা ব্যবহার করার পরিবর্তে সীমাবদ্ধ ক্ষেত্র জিএফ (2) এর উপর সংজ্ঞায়িত করা হয়। একটি গ্রাফের র্যাঙ্ক-প্রস্থ হল বায়াজ্যাসেন্সি ম্যাট্রিক্সের র্যাঙ্কগুলির সর্বাধিক, এই সর্বাধিককে হ্রাস করার জন্য নির্বাচিত একটি ক্লাস্টারিংয়ের জন্য। র্যাঙ্ক-প্রস্থ ক্লিক-প্রস্থের সাথে ঘনিষ্ঠভাবে সম্পর্কিত, যেখানে ক্লিক-প্রস্থ। যাইহোক, বড় চক্র-প্রস্থের গ্রাফের জন্য চক্র-প্রস্থ গণনা করা এনপি-কঠিন, এবং এর পরামিতিগত জটিলতা অজানা। বিপরীতে, র্যাঙ্ক-প্রস্থ সর্বাধিক একটি ধ্রুবক কিনা তা পরীক্ষা করতে বহুপদী সময় লাগে এবং এমনকি যখন র্যাঙ্ক-প্রস্থ ধ্রুবক না হয় তখনও এটি বহুপদী সময়ে একটি ধ্রুবক আনুমানিক অনুপাত সহ আনুমানিক হতে পারে। এই কারণে, র্যাঙ্ক-প্রস্থকে ক্লিক-প্রস্থের জন্য আরও সহজে গণনা করা বিকল্প হিসাবে ব্যবহার করা যেতে পারে। উচ্চ র্যাঙ্ক-প্রস্থের গ্রাফের একটি পরিবারের উদাহরণ বর্গাকার গ্রিড গ্রাফ দ্বারা সরবরাহ করা হয়। একটি গ্রিড গ্রাফের জন্য, র্যাঙ্ক-প্রস্থ ঠিক। তথ্যসূত্র গ্রাফ ক্ষুদ্র তত্ত্ব রৈখিক বীজগণিত