|
template<class CONTAINER > |
bool | checkIndependentSet (const Graph &graph, const CONTAINER &nodes) const |
| Checks if subgraph induced by the given nodes forms an independent set. More...
|
|
virtual void | cliqueRemoval (const Graph &graph, List< node > &independentSet) const |
| Applies the clique removal algorithm for finding a large independent set in a given graph. More...
|
|
virtual void | createBuckets (const Graph &graph, int size, Array< Array< node >> &buckets) const |
| Creates a partitioning of the node set into buckets of a given size. More...
|
|
virtual int | getMaximumDegreeNode (const Graph &graph, node &maxDegreeNode) const |
| Searches for a maximum degree node in the graph. More...
|
|
virtual int | getMaximumDegreeNodes (const Graph &graph, List< node > &maxDegreeNodes) const |
| Searches for all nodes with maximum degree in the graph. More...
|
|
virtual NodeColor | getMaximumNodeColor (NodeArray< NodeColor > &colors) |
| Calculates the maximum node color index used in a certain node coloring. More...
|
|
virtual int | getMinimumDegreeNode (const Graph &graph, node &minDegreeNode) const |
| Searches for a minimum degree node in the graph. More...
|
|
virtual int | getMinimumDegreeNodes (const Graph &graph, List< node > &minDegreeNodes) const |
| Searches for all nodes with minimum degree in the graph. More...
|
|
int | getNeighborDegrees (const node &v) const |
| Calculates the sum of neighbor nodes degrees for a given node v. More...
|
|
template<class LISTITERATOR > |
void | getNeighbors (const Graph &graph, LISTITERATOR nodes, List< node > &neighbors) const |
| Calculates the set of neighbors Y for a given set of nodes X. More...
|
|
template<class LISTITERATOR > |
void | getNeighborsComplement (const Graph &graph, LISTITERATOR nodes, List< node > &complementNeighbors) const |
| Calculates the set of complement neighbors Y for a given set of nodes X. More...
|
|
template<class LISTITERATOR > |
void | mergeNodeLists (const Graph &graph, LISTITERATOR firstList, LISTITERATOR secondList, List< node > &mergedList) const |
| Merges two lists of nodes and deletes the duplicates. More...
|
|
virtual void | ramseyAlgorithm (const Graph &graph, List< node > &clique, List< node > &independentSet) const |
| Performs the Ramsey algorithm for finding heuristically large cliques and independents sets in a graph. More...
|
|
virtual void | reverseNodeTable (const Graph &graphOrig, const Graph &graphNew, const NodeArray< node > &orig2New, NodeArray< node > &new2Orig) const |
| Reverses the mapping between the nodes sets of a graph and a subgraph. More...
|
|
int | searchBinary (SearchWrapper *searchWrapper, int start, int end) const |
| Performs a binary search in a specified range with a given oracle. More...
|
|
int | searchLinear (SearchWrapper *searchWrapper, int start, int end) const |
| Performs a linear search in a specified range with a given oracle. More...
|
|
int | searchWigderson (SearchWrapper *searchWrapper) const |
| Performs a the search procedure specified by Wigderson. More...
|
|
RamseyProcedure | m_ramseyProcedure |
| The RamseyProcedure to be used to select nodes. More...
|
|
Approximation algorithms for the node coloring problem in graphs.
This class implements the approximation given by Johnson which tries to find heuristically large independent sets one other the other.
Definition at line 43 of file NodeColoringJohnson.h.