MaxDDBS
ಮ್ಯಾಕ್ಸಿಮಮ್ ಡಿಗ್ರಿ-ಅಂಡ್-ಡಯಾಮೀಟರ್-ಬೌಂಡೆಡ್ ಸಬ್ಗ್ರಾಫ್ ಪ್ರಾಬ್ಲಮ್ (ಮ್ಯಾಕ್ಸ್ಡಿಡಿಬಿಎಸ್) ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಒಂದು ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸಂಪರ್ಕಿತ ಆತಿಥೇಯ ಗ್ರಾಫ್ G, ಡಿಗ್ರಿ d ಗೆ ಮೇಲಿನ ಮಿತಿ ಮತ್ತು ವ್ಯಾಸ k ಗೆ ಮೇಲಿನ ಮಿತಿಯನ್ನು ನೀಡಿದರೆ, ನಾವು G ಯ ಅತಿದೊಡ್ಡ ಉಪಗ್ರಾಫ್ S ಅನ್ನು ಗರಿಷ್ಠ ಡಿಗ್ರಿ d ಮತ್ತು ಗರಿಷ್ಠ ವ್ಯಾಸ k ಅನ್ನು ಹುಡುಕುತ್ತೇವೆ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಡಿಗ್ರಿ-ವ್ಯಾಸದ ಉಪಗ್ರಾಫ್ ಸಮಸ್ಯೆ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ, ಏಕೆಂದರೆ ಇದು ಡಿಗ್ರಿ ವ್ಯಾಸದ ಸಮಸ್ಯೆಯನ್ನು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಹೊಂದಿರುತ್ತದೆ (ಅಂದರೆ, ಸಾಕಷ್ಟು ದೊಡ್ಡ ಸಂಪೂರ್ಣ ಗ್ರಾಫ್ ಅನ್ನು ಹೋಸ್ಟ್ ಗ್ರಾಫ್ ಆಗಿ ತೆಗೆದುಕೊಳ್ಳುವ ಮೂಲಕ). ಡಿಗ್ರಿ-ವ್ಯಾಸದ ಸಮಸ್ಯೆಯ ನೈಸರ್ಗಿಕ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದ್ದರೂ, ಮ್ಯಾಕ್ಸ್ಡಿಡಿಬಿಎಸ್ ಅನ್ನು 2011 ರಲ್ಲಿ ಮಾತ್ರ ತನಿಖೆ ಮಾಡಲು ಪ್ರಾರಂಭಿಸಲಾಯಿತು, ಆದರೆ ಡಿಗ್ರಿ-ವ್ಯಾಸದ ಸಮಸ್ಯೆಯ ಸಂಶೋಧನೆಯು 1960 ರಿಂದ ಸಕ್ರಿಯವಾಗಿದೆ. ಅದರ ಗಣನೆಯ ಸಂಕೀರ್ಣತೆಗೆ ಸಂಬಂಧಿಸಿದಂತೆ, ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ, ಮತ್ತು ಎಪಿಎಕ್ಸ್ನಲ್ಲಿ ಅಲ್ಲ (ಅಂದರೆ. ಇದನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಸ್ಥಿರ ಅಂಶದೊಳಗೆ ಅಂದಾಜು ಮಾಡಲು ಸಾಧ್ಯವಿಲ್ಲ). ಉಲ್ಲೇಖಗಳು ಕಾಂಬಿನೇಟರಿಕ್ಸ್ ವಿಕಿ A.Dekker, H.Perez-Roses, G.Pineda-Villavicencio, ಮತ್ತು P.Watters ನಲ್ಲಿರುವ ಮ್ಯಾಕ್ಸ್ಡಿಡಿಬಿಎಸ್ ಪುಟ. ಗರಿಷ್ಠ ಪದವಿ ಮತ್ತು ವ್ಯಾಸ-ಸೀಮಿತ ಉಪಗ್ರಫ್ ಮತ್ತು ಅದರ ಅನ್ವಯಗಳು. ಜರ್ನಲ್ ಆಫ್ ಮ್ಯಾಥಮೆಟಿಕಲ್ ಮಾಡೆಲಿಂಗ್ ಅಂಡ್ ಅಲ್ಗಾರಿದಮ್ಸ್, 2012. ಡಿಒಐಃ 10.1007/s10852-012-9182-8 M.Miller, H.Perez-Roses, ಮತ್ತು J.Ryan. ಜಾಲರಿಯಲ್ಲಿ ಗರಿಷ್ಠ ಡಿಗ್ರಿ ಮತ್ತು ವ್ಯಾಸದ ಬೌಂಡೆಡ್ ಸಬ್ಗ್ರಾಫ್. ಡಿಸ್ಕ್ರೀಟ್ ಅಪ್ಲೈಡ್ ಮ್ಯಾಥಮ್ಯಾಟಿಕ್ಸ್, 2012. ಡಿ. ಓ. ಐ.: <ಐ. ಡಿ. 1> ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು