Dense subgraph
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಮತ್ತು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ದಟ್ಟವಾದ ಉಪಗ್ರಾಫ್ ಎಂದರೆ ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಅನೇಕ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಉಪಗ್ರಾಫ್. ಇದನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಔಪಚಾರಿಕಗೊಳಿಸಲಾಗಿದೆಃ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ ಆಗಿರಲಿ ಮತ್ತು ಅದರ ಉಪಗ್ರಾಫ್ ಆಗಿರಲಿ. ನಂತರ ಇದರ ಸಾಂದ್ರತೆಯನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ ಸಾಂದ್ರವಾದ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯೆಂದರೆ ಗರಿಷ್ಠ ಸಾಂದ್ರತೆಯ ಸಬ್ಗ್ರಾಫ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು. ಗ್ರಾಫ್ನ ಗರಿಷ್ಠ ದಟ್ಟವಾದ ಸಬ್ಗ್ರಾಫ್ನ ಸಾಂದ್ರತೆಯನ್ನು ಕೆಲವೊಮ್ಮೆ ಅದರ ಸಬ್ಗ್ರಾಫ್ ಸಾಂದ್ರತೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. 1984ರಲ್ಲಿ, ಆಂಡ್ರ್ಯೂ ವಿ. ಗೋಲ್ಡ್ಬರ್ಗ್ ಅವರು ಗರಿಷ್ಠ ಹರಿವಿನ ತಂತ್ರವನ್ನು ಬಳಸಿಕೊಂಡು ಗರಿಷ್ಠ ಸಾಂದ್ರತೆಯ ಉಪಗ್ರ್ಯಾಫ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಬಹುಪದೀಯ ಸಮಯದ ಕ್ರಮಾವಳಿಯನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು. ಇದನ್ನು 1989 ರಲ್ಲಿ ಗ್ಯಾಲೋ, ಗ್ರಿಗೋರಿಯಾಡಿಸ್ ಮತ್ತು ಟಾರ್ಜನ್ ಅವರು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ನಿರ್ವಹಿಸಲು ಸುಧಾರಿಸಿದ್ದಾರೆ. ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸರಳವಾದ ಎಲ್ಪಿ ಯನ್ನು 2000 ರಲ್ಲಿ ಚಾರಿಕರ್ ನೀಡಿದರು. ಸಬ್ಗ್ರಾಫ್ ಸಾಂದ್ರತೆಯು ಆರ್ಬೋರಿಸಿಟಿ ಮತ್ತು ಗ್ರಾಫ್ ಡಿಜೆನೆರಸಿಗೆ ಸಂಬಂಧಿಸಿದ ಕಲ್ಪನೆಗೆ ಅಸಿಂಪ್ಟೋಟಿಕ್ ಆಗಿದೆ. ದಟ್ಟವಾದ ಉಪಗ್ರ್ಯಾಫ್ ದಟ್ಟವಾದ ಉಪಗ್ರ್ಯಾಫ್ ಸಮಸ್ಯೆಯ ಮೇಲೆ ಅನೇಕ ವ್ಯತ್ಯಾಸಗಳಿವೆ. ಅವುಗಳಲ್ಲಿ ಒಂದು ದಟ್ಟವಾದ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯಾಗಿದೆ, ಅಲ್ಲಿ ನಿಖರವಾದ ಶೃಂಗಗಳ ಮೇಲೆ ಗರಿಷ್ಠ ಸಾಂದ್ರತೆಯ ಸಬ್ಗ್ರಾಫ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಇದರ ಉದ್ದೇಶವಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯು ಗುಂಪಿನ ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯಗೊಳಿಸುತ್ತದೆ ಮತ್ತು ಆದ್ದರಿಂದ ಸಾಮಾನ್ಯ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ. ಪ್ರತಿಯೊಂದಕ್ಕೂ ಅನುಪಾತದೊಳಗೆ ದಟ್ಟವಾದ ಉಪಗ್ರ್ಯಾಫ್ ಅನ್ನು ಅಂದಾಜು ಮಾಡುವ ಬಹುಪದ ಅಲ್ಗಾರಿದಮ್ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಆದರೆ ಘಾತೀಯ ಸಮಯದ ಊಹೆಯು ತಪ್ಪಾಗಿರದ ಹೊರತು ಇದು ಬಹುಪದ ಸಮಯದಲ್ಲಿ-ಹೊಂದಾಣಿಕೆಯನ್ನು ಒಪ್ಪಿಕೊಳ್ಳುವುದಿಲ್ಲ. ಈ ಸಮಸ್ಯೆಗೆ ಯಾವುದೇ ಪಿ. ಟಿ. ಎ. ಎಸ್ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ ಎಂಬ ದುರ್ಬಲ ಊಹೆಯ ಅಡಿಯಲ್ಲಿ. ಈ ಸಮಸ್ಯೆಯು ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಕಾರ್ಡಲ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಎನ್ಪಿ-ಕಠಿಣವಾಗಿ ಉಳಿದಿದೆ ಆದರೆ ಮರಗಳು ಮತ್ತು ವಿಭಜಿತ ಗ್ರಾಫ್ಗಳಿಗೆ ಬಹುಪದವಾಗಿದೆ. (ಸರಿಯಾದ) ಮಧ್ಯಂತರ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಅಥವಾ ಬಹುಪದಿಯೇ ಎಂಬುದು ಮುಕ್ತವಾಗಿದೆ; ಆದಾಗ್ಯೂ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ಸಬ್ಗ್ರಾಫ್ ಅನ್ನು ಸಂಪರ್ಕಿಸಬೇಕಾದ ಸಮಸ್ಯೆಯ ವ್ಯತ್ಯಾಸವು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದೆ. ಹೆಚ್ಚಿನ ಶೃಂಗಗಳಲ್ಲಿ ಗರಿಷ್ಠ ಸಾಂದ್ರತೆಯ ಉಪ ನಕ್ಷೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಅತ್ಯಂತ ದಟ್ಟವಾದ ಸಮಸ್ಯೆಯ ಉದ್ದೇಶವಾಗಿದೆ. ಆಂಡರ್ಸನ್ ಮತ್ತು ಚೆಲ್ಲಾಪಿಲ್ಲಾ ಈ ಸಮಸ್ಯೆಗೆ ಒಂದು-ಹೊಂದಾಣಿಕೆ ಇದ್ದರೆ ಅದು ದಟ್ಟವಾದ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಗೆ-ಹೊಂದಾಣಿಕೆಗೆ ಕಾರಣವಾಗುತ್ತದೆ ಎಂದು ತೋರಿಸಿದರು. ದಟ್ಟವಾದ ಕನಿಷ್ಠ ಉಪಗ್ರ್ಯಾಫ್ ಕನಿಷ್ಠ ದಟ್ಟವಾದ ಸಮಸ್ಯೆಯನ್ನು ಹೆಚ್ಚಿನ ಉಪಗ್ರ್ಯಾಫ್ ಸಮಸ್ಯೆಯಲ್ಲಿ ದಟ್ಟವಾದಂತೆಯೇ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆ. ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಪೂರ್ಣವಾಗಿದೆ, ಆದರೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ 2-ಹೊಂದಾಣಿಕೆಯನ್ನು ಒಪ್ಪಿಕೊಳ್ಳುತ್ತದೆ. ಇದಲ್ಲದೆ, ಈ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಮೂಲಭೂತವಾಗಿ ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮವಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಕೆಲವು ಪುರಾವೆಗಳಿವೆಃ ಸಣ್ಣ ಸೆಟ್ ವಿಸ್ತರಣೆಯ ಊಹೆಯನ್ನು ಊಹಿಸಿಕೊಳ್ಳಿ (ವಿಶಿಷ್ಟ ಆಟದ ಊಹೆಗೆ ನಿಕಟವಾಗಿ ಸಂಬಂಧಿಸಿರುವ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆಯ ಊಹೆ), ನಂತರ ಪ್ರತಿ ಸ್ಥಿರಾಂಕದ ಅಂಶದೊಳಗೆ ಸಮಸ್ಯೆಯನ್ನು ಅಂದಾಜು ಮಾಡುವುದು ಎನ್ಪಿ-ಕಠಿಣವಾಗಿದೆ. - ಕ್ಲಿಕ್ ಡೆನ್ಸೆಸ್ಟ್ ಸಬ್ಗ್ರಾಫ್ ಚರಲಾಂಪೋಸ್ ಸೌರಾಕಾಕಿಸ್-ಕ್ಲಿಕ್ ಡೆನ್ಸೆಸ್ಟ್ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಚಯಿಸಿದರು. ದಟ್ಟವಾದ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯ ಈ ಬದಲಾವಣೆಯು ಪ್ರಚೋದಿತ ಗುಂಪುಗಳ ಸರಾಸರಿ ಸಂಖ್ಯೆಯನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವ ಗುರಿಯನ್ನು ಹೊಂದಿದೆ, ಅಲ್ಲಿ-ಕ್ಲಿಕ್ಗಳ ಗುಂಪನ್ನು ಪ್ರಚೋದಿಸಲಾಗುತ್ತದೆ. ದಟ್ಟವಾದ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯನ್ನು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಪಡೆಯಲಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಈ ಸಾಮಾನ್ಯೀಕರಣವು ದೊಡ್ಡ ಪ್ರಮಾಣದ ನೈಜ-ಪ್ರಪಂಚದ ಜಾಲಗಳಿಂದ ದೊಡ್ಡ ಹತ್ತಿರದ ಕ್ಲಿಕ್ಗಳನ್ನು ಹೊರತೆಗೆಯಲು ಪ್ರಾಯೋಗಿಕವಾಗಿ ಯಶಸ್ವಿ ಬಹು-ಸಮಯದ ವಿಧಾನವನ್ನು ಒದಗಿಸುತ್ತದೆ. ಸ್ಥಳೀಯವಾಗಿ ಅತ್ಯಂತ ದಟ್ಟವಾದ ಉಪ-ಗ್ರಾಫ್ ಕಿನ್ ಮತ್ತು ಇತರರು. ಅಗ್ರ-ಕೆ ಸ್ಥಳೀಯವಾಗಿ ದಟ್ಟವಾದ ಉಪಗ್ರಾಫ್ಗಳ ಆವಿಷ್ಕಾರದ ಸಮಸ್ಯೆಯನ್ನು ಗ್ರಾಫ್ನಲ್ಲಿ ಪರಿಚಯಿಸಲಾಯಿತು, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಗ್ರಾಫ್ನಲ್ಲಿ ಅದರ ಸ್ಥಳೀಯ ಪ್ರದೇಶದಲ್ಲಿ ಹೆಚ್ಚಿನ ಸಾಂದ್ರತೆಯನ್ನು ಸಾಧಿಸುತ್ತದೆಃ ಇದು ಒಂದೇ ಅಥವಾ ದೊಡ್ಡ ಸಾಂದ್ರತೆಯೊಂದಿಗೆ ಯಾವುದೇ ಸೂಪರ್ಗ್ರಾಫ್ನಲ್ಲಿ ಒಳಗೊಂಡಿಲ್ಲ, ಅಥವಾ ಸಾಂದ್ರತೆಯೊಂದಿಗೆ ಉಪಗ್ರಾಫ್ಗಳನ್ನು ಒಳಗೊಂಡಿಲ್ಲ ಉಳಿದ ಸ್ಥಳೀಯ ದಟ್ಟವಾದ ಉಪಗ್ರಾಫ್ಗಳೊಂದಿಗೆ ಸಡಿಲವಾಗಿ ಸಂಪರ್ಕ ಹೊಂದಿದೆ. ದಟ್ಟವಾದ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆಯನ್ನು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿ ಪಡೆಯಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಗ್ರಾಫ್ನಲ್ಲಿನ ಸ್ಥಳೀಯವಾಗಿ ದಟ್ಟವಾದ ಉಪಗ್ರಾಫ್ಗಳ ಗುಂಪನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ಉಲ್ಲೇಖಗಳು ಹೆಚ್ಚಿನ ಓದುವಿಕೆ. .. .. .. .. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ