gistfile1.txt

digraph mainmap {
    resolution = 72;
node [fontsize = 10];
edge [fontsize = 9];
overlap = false;
sep=0.4
splines=true;xSatisfiability [label= "SATISFIABILITY" URL= "http://en.wikipedia.org/wiki/Satisfiability"style="bold", shape="ellipse", peripheries="2", fontsize ="14"];
xCircuitSatisfiability [label= "CIRCUIT SATISFIABILITY" URL= "" style ="filled", fillcolor ="#eeeeee" style="bold", shape="ellipse", peripheries="2", fontsize ="14"];
xMaxCut [label= "MAX CUT" URL= "http://en.wikipedia.org/wiki/Cut_(graph_theory)#Minimal_and_maximal_cuts"];
xJobSequencing [label= "JOB SEQUENCING" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xSubsetSum [label= "SUBSET-SUM" URL= "http://en.wikipedia.org/wiki/Subset_sum_problem"];
xKnapsack [label= "KNAPSACK" URL= "http://en.wikipedia.org/wiki/Knapsack_problem"];
x3dimensionalMatching [label= "3-DIMENSIONAL MATCHING" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xSteinerTree [label= "STEINER TREE" URL= "http://en.wikipedia.org/wiki/Steiner_tree"];
xHittingSet [label= "HITTING SET" URL= "http://en.wikipedia.org/wiki/Hitting_set"];
xExactCover [label= "EXACT COVER" URL= "http://en.wikipedia.org/wiki/Exact_cover"];
xCliqueCover [label= "CLIQUE COVER" URL= "http://en.wikipedia.org/wiki/Clique_cover"];
xChromaticNumber [label= "CHROMATIC NUMBER" URL= "http://en.wikipedia.org/wiki/Graph_coloring"];
x3Satisfiability [label= "3-SATISFIABILITY" URL= "http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability"];
xUndirectedHamiltonianCircuit [label= "UNDIRECTED HAMILTONIAN CIRCUIT" URL= "http://en.wikipedia.org/wiki/Hamiltonian_path_problem"];
xDirectedHamiltonianCircuit [label= "DIRECTED HAMILTONIAN CIRCUIT" URL= "http://en.wikipedia.org/wiki/Hamiltonian_path_problem"];
xFeedbackArcSet [label= "FEEDBACK ARC SET" URL= "http://en.wikipedia.org/wiki/Feedback_arc_set"];
xFeedbackNodeSet [label= "FEEDBACK NODE SET" URL= "http://en.wikipedia.org/wiki/Feedback_vertex_set"];
xSetCovering [label= "SET COVERING" URL= "http://en.wikipedia.org/wiki/Set_cover_problem"];
xVertexCover [label= "VERTEX COVER" URL= "http://en.wikipedia.org/wiki/Vertex_cover_problem"];
x01IntegerProgramming [label= "0-1-INTEGER PROGRAMMING" URL= "http://en.wikipedia.org/wiki/Integer_linear_programming"];
xClique [label= "CLIQUE" URL= "http://en.wikipedia.org/wiki/Clique_problem"];
xSetPacking [label= "SET PACKING" URL= "http://en.wikipedia.org/wiki/Set_packing"];
xPartition [label= "PARTITION" URL= "http://en.wikipedia.org/wiki/Partition_problem"];
xSubgraphIsomorphism [label= "SUBGRAPH ISOMORPHISM" URL= "http://en.wikipedia.org/wiki/Subgraph_isomorphism_problem"];
xIndependentNodeSet [label= "INDEPENDENT NODE SET" URL= "http://en.wikipedia.org/wiki/Independent_set_problem"];
xBinPacking [label= "BIN PACKING" URL= "http://en.wikipedia.org/wiki/Bin_packing_problem"];
xTravelingSalesman [label= "TRAVELING SALESMAN" URL= "http://en.wikipedia.org/wiki/Travelling_salesman_problem"];
xTravelingSalesmantriangleinequality [label= "TRAVELING SALESMAN \n(triangle inequality)" URL= "http://en.wikipedia.org/wiki/Travelling_salesman_problem"];
xDominatingSet [label= "DOMINATING SET" URL= "http://en.wikipedia.org/wiki/Dominating_set_problem"];
x3Colourability [label= "3-COLOURABILITY" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xkPartition [label= "K-PARTITION" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xMax2SAT [label= "MAX 2-SAT" URL= "http://portal.acm.org/citation.cfm?id=803884"];
xMaxCutsimple [label= "MAX CUT \n(simple)" URL= "http://portal.acm.org/citation.cfm?id=803884"];
xOptimalLinearAssignmentsimple [label= "OPTIMAL LINEAR ASSIGNMENT\n(simple)" URL= "http://portal.acm.org/citation.cfm?id=803884"];
xOptimalLinearAssignment [label= "OPTIMAL LINEAR ASSIGNMENT" URL= "http://portal.acm.org/citation.cfm?id=803884"];
xDomaticNumber [label= "DOMATIC NUMBER" URL= "http://en.wikipedia.org/wiki/Domatic_number"];
xTetrisoffline [label= "TETRIS\n(offline)" URL= "http://arxiv.org/pdf/cs/0210020v1"];
xkMinesweeper [label= "K-MINESWEEPER" URL= "http://people.reed.edu/~jimfix/papers/1MINESWEEPER.pdf"];
xMinesweeper [label= "MINESWEEPER" URL= "http://en.wikipedia.org/wiki/Minesweeper_(computer_game)"];
xPhutball [label= "PHUTBALL" URL= "http://en.wikipedia.org/wiki/Phutball"];
xAchromaticNumber [label= "ACHROMATIC NUMBER" URL= "http://en.wikipedia.org/wiki/Achromatic_number"];
xMinimumMaximalMatching [label= "MINIMUM MAXIMAL MATCHING" URL= "http://link.aip.org/link/?SMJMAP/38/364/1"];
xMonochromaticTriangle [label= "MONOCHROMATIC TRIANGLE" URL= "http://en.wikipedia.org/wiki/Monochromatic_triangle"];
xPartialFeedbackEdgeSet [label= "PARTIAL FEEDBACK EDGE SET" URL= "http://portal.acm.org/citation.cfm?id=804355"];
xPartitionintoTriangles [label= "PARTITION INTO TRIANGLES" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xPartitionintoIsomorphicSubgraphs [label= "PARTITION INTO ISOMORPHIC SUBGRAPHS" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xPartitionintoHamiltonianSubgraphs [label= "PARTITION INTO HAMILTONIAN SUBGRAPHS" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xPartitionintoForests [label= "PARTITION INTO FORESTS" URL= "" style ="filled", fillcolor ="#eeeeee" ];
x3Satisfiabilitynotallequal [label= "3-SATISFIABILITY\n(not all equal)" URL= "http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability"];
xPartitionintoperfectMatchings [label= "PARTITION INTO PERFECT MATCHINGS" URL= "http://portal.acm.org/citation.cfm?id=804350"];
xCoveringbyCliques [label= "COVERING BY CLIQUES" URL= "http://portal.acm.org/citation.cfm?id=359340.359346"];
xCoveringbycompletebipartitesubgraphs [label= "COVERING BY COMPLETE BIPARTITE SUBGRAPHS" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xInducedSubgraphwithPropertyPi [label= "INDUCED SUBGRAPH WITH PROPERTY PI" URL= "http://www.csc.kth.se/~viggo/wwwcompendium/node36.html"];
xInducedconnectedSubgraphwithPropertyPi [label= "INDUCED CONNECTED SUBGRAPH WITH PROPERTY PI" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xInducedPath [label= "INDUCED PATH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xBalancedCompleteBipartiteSubgraph [label= "BALANCED COMPLETE BIPARTITE SUBGRAPH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xBipartiteSubgraph [label= "BIPARTITE SUBGRAPH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xDegreeBoundedConnectedSubgraph [label= "DEGREE-BOUNDED CONNECTED SUBGRAPH" URL= "http://www.csc.kth.se/~viggo/wwwcompendium/node41.html"];
xHamiltonianPath [label= "HAMILTONIAN PATH" URL= "http://en.wikipedia.org/wiki/Hamiltonian_path"];
xPlanarSubgraph [label= "PLANAR SUBGRAPH" URL= "http://www.nada.kth.se/~viggo/wwwcompendium/node42.html"];
xEdgeSubgraph [label= "EDGE SUBGRAPH" URL= "http://www.nada.kth.se/~viggo/wwwcompendium/node46.html"];
xTransitiveSubgraph [label= "TRANSITIVE SUBGRAPH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xUniconnectedSubgraph [label= "UNICONNECTED SUBGRAPH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xMinimumkConnectedSubgraph [label= "MINIMUM K-CONNECTED SUBGRAPH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xCubicSubgraph [label= "CUBIC SUBGRAPH" URL= "http://portal.acm.org/citation.cfm?id=892117"];
xMinimumEquivalentDigraph [label= "MINIMUM EQUIVALENT DIGRAPH" URL= "http://www.nada.kth.se/~viggo/wwwcompendium/node49.html"];
xHamiltonianCompletion [label= "HAMILTONIAN COMPLETION" URL= "http://en.wikipedia.org/wiki/Hamiltonian_completion"];
xIntervalGraphCompletion [label= "INTERVAL GRAPH COMPLETION" URL= "http://www.nada.kth.se/~viggo/wwwcompendium/node50.html"];
xPathGraphCompletion [label= "PATH GRAPH COMPLETION" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xBandwidthgraphtheory [label= "BANDWIDTH\n(graph theory)" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xDirectedBandwidth [label= "DIRECTED BANDWIDTH" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xOptimalLinearArrangementdirected [label= "OPTIMAL LINEAR ARRANGEMENT \n(directed)" URL= "" style ="filled", fillcolor ="#eeeeee" ];
xOptimalLinearArrangement [label= "OPTIMAL LINEAR ARRANGEMENT" URL= "" style ="filled", fillcolor ="#eeeeee" ];
x01IntegerProgramming -> xSatisfiability [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xClique -> xSatisfiability [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xSetPacking -> xClique [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xVertexCover -> xClique [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xSetCovering -> xVertexCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xFeedbackNodeSet -> xVertexCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xFeedbackArcSet -> xVertexCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xDirectedHamiltonianCircuit -> xVertexCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xUndirectedHamiltonianCircuit -> xDirectedHamiltonianCircuit [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xChromaticNumber -> x3Satisfiability [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xCliqueCover -> xChromaticNumber [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xExactCover -> xChromaticNumber [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xHittingSet -> xExactCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xSteinerTree -> xExactCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
x3dimensionalMatching -> xExactCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xKnapsack -> xExactCover [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xJobSequencing -> xKnapsack [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xSubsetSum -> xKnapsack [URL = "" label = "" color ="gray" ];
xPartition -> xSubsetSum [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
xMaxCut -> xPartition [URL = "http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" label = "Karp\n1972" ];
x3Satisfiability -> xSatisfiability [URL = "http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz" label = "Cook\n1971" ];
xSubgraphIsomorphism -> x3Satisfiability [URL = "http://www.cs.toronto.edu/~sacook/homepage/1971.pdf.gz" label = "Cook\n1971" ];
xSatisfiability -> xCircuitSatisfiability [URL = "" label = "" color ="gray" ];
xUndirectedHamiltonianCircuit -> xSubgraphIsomorphism [URL = "" label = "" color ="gray" ];
xIndependentNodeSet -> xClique [URL = "" label = "" color ="gray" ];
xTravelingSalesmantriangleinequality -> xUndirectedHamiltonianCircuit [URL = "http://portal.acm.org/citation.cfm?id=803626&dl=GUIDE&coll=GUIDE&CFID=23701820&CFTOKEN=21874286" label = "Garey Graham Johnson\n1976" ];
xTravelingSalesman -> xDirectedHamiltonianCircuit [URL = "" label = "" color ="gray" ];
xkPartition -> xPartition [URL = "" label = "" color ="gray" ];
xBinPacking -> xPartition [URL = "" label = "" color ="gray" ];
xDominatingSet -> xVertexCover [URL = "http://cat.inist.fr/?aModele=afficheN&cpsidt=8937489" label = "Yehuda Moran\n1984" ];
x3Colourability -> xChromaticNumber [URL = "" label = "" color ="gray" ];
xMax2SAT -> x3Satisfiability [URL = "http://portal.acm.org/citation.cfm?id=803884" label = "Garey Johnson Stockmeyer\n1974" ];
xMaxCutsimple -> xMax2SAT [URL = "http://portal.acm.org/citation.cfm?id=803884" label = "Garey Johnson Stockmeyer\n1974" ];
xOptimalLinearAssignmentsimple -> xMaxCutsimple [URL = "http://portal.acm.org/citation.cfm?id=803884" label = "Garey Johnson Stockmeyer\n1974" ];
xOptimalLinearAssignment -> xOptimalLinearAssignmentsimple [URL = "http://portal.acm.org/citation.cfm?id=803884" label = "Garey Johnson Stockmeyer\n1974" ];
xJobSequencing -> xSubsetSum [URL = "" label = "" color ="gray" ];
xVertexCover -> x3Satisfiability [URL = "" label = "" color ="gray" ];
xDomaticNumber -> x3Satisfiability [URL = "http://portal.acm.org/citation.cfm?id=804034" label = "Johnson\n1974" ];
xTetrisoffline -> xkPartition [URL = "http://arxiv.org/pdf/cs/0210020v1" label = "E. Demaine Hohenberger Liben-Nowell\n2008" ];
xkMinesweeper -> xCircuitSatisfiability [URL = "http://people.reed.edu/~jimfix/papers/1MINESWEEPER.pdf" label = "Fix McPhail\n2004" ];
xMinesweeper -> xCircuitSatisfiability [URL = "" label = "Kaye\n2000" ];
xPhutball -> x3Satisfiability [URL = "http://www.msri.org/publications/books/Book42/files/dephut.pdf" label = "M. Demaine E. Demaine Eppstein\n2002" ];
xMinimumMaximalMatching -> xVertexCover [URL = "http://link.aip.org/link/?SMJMAP/38/364/1" label = "Yannakakis Gavril\n1978" ];
xAchromaticNumber -> xMinimumMaximalMatching [URL = "http://link.aip.org/link/?SMJMAP/38/364/1" label = "Yannakakis Gavril\n1978" ];
xMonochromaticTriangle -> x3Satisfiability [URL = "" label = "" color ="gray" ];
xPartialFeedbackEdgeSet -> xVertexCover [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xPartitionintoTriangles -> x3dimensionalMatching [URL = "" label = "" color ="gray" ];
xPartitionintoIsomorphicSubgraphs -> x3dimensionalMatching [URL = "" label = "" color ="gray" ];
xPartitionintoHamiltonianSubgraphs -> x3Satisfiability [URL = "http://www.google.de/search?q=the+complexity+of+computing+the+permanent" label = "Valiant\n1977" ];
xPartitionintoForests -> x3Colourability [URL = "" label = "" color ="gray" ];
x3Satisfiabilitynotallequal -> x3Satisfiability [URL = "http://portal.acm.org/citation.cfm?id=804350&dl=GUIDE," label = "Schaefer\n1978" ];
xPartitionintoperfectMatchings -> x3Satisfiabilitynotallequal [URL = "http://portal.acm.org/citation.cfm?id=804350&dl=GUIDE," label = "Schaefer\n1978" ];
xCoveringbyCliques -> xCliqueCover [URL = "http://portal.acm.org/citation.cfm?id=359340.359346" label = "Kou Stockmeyer Wong\n1978" ];
xCoveringbycompletebipartitesubgraphs -> xCliqueCover [URL = "" label = "Orlin\n1976" ];
xInducedSubgraphwithPropertyPi -> x3Satisfiability [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xInducedconnectedSubgraphwithPropertyPi -> x3Satisfiability [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xInducedPath -> x3Satisfiability [URL = "" label = "" color ="gray" ];
xBalancedCompleteBipartiteSubgraph -> xClique [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xBipartiteSubgraph -> xMax2SAT [URL = "" label = "" color ="gray" ];
xHamiltonianPath -> xVertexCover [URL = "" label = "" color ="gray" ];
xDegreeBoundedConnectedSubgraph -> xHamiltonianPath [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xPlanarSubgraph -> xHamiltonianPath [URL = "" label = "Liu Geldmacher\n1978" ];
xEdgeSubgraph -> x3Satisfiability [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xTransitiveSubgraph -> xBipartiteSubgraph [URL = "http://portal.acm.org/citation.cfm?id=804355" label = "Yannakakis\n1978" ];
xUniconnectedSubgraph -> xVertexCover [URL = "http://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-092-76.pdf" label = "Maheshwari\n1976" ];
xMinimumkConnectedSubgraph -> xUndirectedHamiltonianCircuit [URL = "" label = "" color ="gray" ];
xCubicSubgraph -> x3Colourability [URL = "http://portal.acm.org/citation.cfm?id=892117" label = "" color ="gray" ];
xMinimumEquivalentDigraph -> xDirectedHamiltonianCircuit [URL = "http://www.cise.ufl.edu/~sahni/papers/comp.pdf" label = "Sahni\n1974" ];
xHamiltonianCompletion -> xUndirectedHamiltonianCircuit [URL = "" label = "" color ="gray" ];
xIntervalGraphCompletion -> xOptimalLinearAssignment [URL = "" label = "" color ="gray" ];
xPathGraphCompletion -> xIntervalGraphCompletion [URL = "" label = "" color ="gray" ];
xBandwidthgraphtheory -> xkPartition [URL = "http://www.springerlink.com/content/ch81377764427164/" label = "Papadimitriou\n1976" ];
xDirectedBandwidth -> xkPartition [URL = "http://www.jstor.org/pss/2100947" label = "Garey Graham Johnson Knuth\n1978" ];
xOptimalLinearArrangementdirected -> xOptimalLinearArrangement [URL = "" label = "Even Shiloach\n1975" ];
xOptimalLinearArrangement -> xMaxCutsimple [URL = "" label = "" color ="gray" ];

}