Computing desk
< February 27	<< Jan \| February \| Mar >>	Current desk >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 28

Algorithm to find largest complete subgraph

Given a connected graph, I need to find the largest subgraph that is complete (i.e. in the subgraph, each vertex is connected to each other vertex). There is one vertex, I'll call the origin, that is connected to all other vertices in the graph. Otherwise, the adjacency matrix is less than half full. I need to find the largest complete subgraph that contains the origin vertex.

I've thought of taking, in turn, each vertex, v, that is connected to the origin and do a depth-first search (DFS) from there. Doing the DFS, keep track of the connected subgraph. When visiting each new vertex, see if it is connected to all of the other members found in the complete subgraph. If it is connected to all of them, add it; otherwise, mark it as visited.

The problem, though, is that it seems to me that there could be other paths that involve points that have been visited but not in the complete subgraph that was found, but could be part of a larger complete subgraph. Of course, after finishing the DFS, you could mark all vertices as not visited and start down a different path from the vertex that is connected to the origin. But is doing this for every point that is connected to the current vertex v, but is that sufficient to guarantee that the largest complete subgraph is found? (It doesn't seem sufficient to me.) Bubba73 ^{You talkin' to me?} 04:11, 28 February 2021 (UTC)[reply]

It just occurred to me that it might be better to take each vertex, v, that is connected to the origin vertex and do a breadth-first search from each v. I haven't had time to think it through. Bubba73 ^{You talkin' to me?} 05:02, 28 February 2021 (UTC)[reply]

See clique problem. 116.86.4.41 (talk) 09:19, 28 February 2021 (UTC)[reply]

In particular, Clique problem § Finding maximum cliques in arbitrary graphs. --Lambiam 12:24, 28 February 2021 (UTC)[reply]

Thank you, I will look into that. Bubba73 ^{You talkin' to me?} 17:51, 28 February 2021 (UTC)[reply]

Well, it looks like the running time is too long for what I wanted to do . Bubba73 ^{You talkin' to me?} 04:58, 2 March 2021 (UTC)[reply]

Windows 10 resolution

My Windows 10 PC occasionally switched the graphic resolution by itself. Every time before, I just rebooted and got back to normal. This time it didn't work. I'm currently at 1440 x 900. All of the other settings I've tried don't look right. When I boot up, the password field is off-center, and once I'm in, a few of the icons on the bottom bar aren't visible because they're too far to the right. Help! Clarityfiend (talk) 20:28, 28 February 2021 (UTC)[reply]

The current highest resolution offered in 1600 x 1200. Not only does that one not work, it's still a lower resolution than what I had before (1900 x nnn, I think). My monitor is 24"? Clarityfiend (talk) 21:18, 28 February 2021 (UTC)[reply]

Fixed it myself. I deleted the generic device driver and rebooted. Clarityfiend (talk) 04:18, 1 March 2021 (UTC)[reply]

Resolved

Windows 10 resolution problem

My Windows 10 PC occasionally switched the graphic resolution by itself. Every time before, I just rebooted and got back to normal. This time it didn't work. I'm currently at 1440 x 900. All of the other settings I've tried don't look right. When I boot up, the password field is off-center, and once I'm in, a few of the icons on the bottom bar aren't visible because they're too far to the right. Help! Clarityfiend (talk) 20:28, 28 February 2021 (UTC)[reply]

I had an edit conflict ... with myself. Clarityfiend (talk) 20:29, 28 February 2021 (UTC)[reply]

Careful! You might go blind! {The poster formerly known as 87.81.230.195} 2.125.75.168 (talk) 18:53, 1 March 2021 (UTC)[reply]