Next: Covering and Partitioning Up: A compendium of NP Previous: Improving the compendium   Index


Graph Theory



  1. Covering and Partitioning
    1. MINIMUM VERTEX COVER
    2. MINIMUM DOMINATING SET
    3. MINIMUM EDGE DOMINATING SET
    4. MINIMUM INDEPENDENT DOMINATING SET
    5. MINIMUM GRAPH COLORING
    6. MAXIMUM ACHROMATIC NUMBER
    7. MINIMUM EDGE COLORING
    8. MINIMUM FEEDBACK VERTEX SET
    9. MINIMUM FEEDBACK ARC SET
    10. MINIMUM MAXIMAL MATCHING
    11. MAXIMUM TRIANGLE PACKING
    12. MAXIMUM H-MATCHING
    13. MINIMUM BOTTLENECK PATH MATCHING
    14. MINIMUM CLIQUE PARTITION
    15. MINIMUM K-CAPACITATED TREE PARTITION
    16. MAXIMUM BALANCED CONNECTED PARTITION
    17. MINIMUM CLIQUE COVER
    18. MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER
    19. MINIMUM VERTEX DISJOINT CYCLE COVER
    20. MINIMUM EDGE DISJOINT CYCLE COVER
    21. MINIMUM CUT COVER
  2. Subgraphs and Supergraphs
    1. MAXIMUM CLIQUE
    2. MAXIMUM INDEPENDENT SET
    3. MAXIMUM INDEPENDENT SEQUENCE
    4. MAXIMUM INDUCED SUBGRAPH WITH PROPERTY P
    5. MINIMUM VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P
    6. MINIMUM EDGE DELETION TO OBTAIN SUBGRAPH WITH PROPERTY P
    7. MAXIMUM INDUCED CONNECTED SUBGRAPH WITH PROPERTY P
    8. MINIMUM VERTEX DELETION TO OBTAIN CONNECTED SUBGRAPH WITH PROPERTY P
    9. MAXIMUM DEGREE-BOUNDED CONNECTED SUBGRAPH
    10. MAXIMUM PLANAR SUBGRAPH
    11. MINIMUM EDGE DELETION K-PARTITION
    12. MAXIMUM K-COLORABLE SUBGRAPH
    13. MAXIMUM SUBFOREST
    14. MAXIMUM EDGE SUBGRAPH
    15. MINIMUM EDGE 2-SPANNER
    16. MAXIMUM K-COLORABLE INDUCED SUBGRAPH
    17. MINIMUM EQUIVALENT DIGRAPH
    18. MINIMUM INTERVAL GRAPH COMPLETION
    19. MINIMUM CHORDAL GRAPH COMPLETION
    20. MINIMUM COLOR SUM
  3. Vertex Ordering
    1. MINIMUM BANDWIDTH
    2. MINIMUM DIRECTED BANDWIDTH
    3. MINIMUM LINEAR ARRANGEMENT
    4. MINIMUM CUT LINEAR ARRANGEMENT
  4. Iso- and Other Morphisms
    1. MAXIMUM COMMON SUBGRAPH
    2. MAXIMUM COMMON INDUCED SUBGRAPH
    3. MAXIMUM COMMON EMBEDDED SUB-TREE
    4. MINIMUM GRAPH TRANSFORMATION
  5. Miscellaneous
    1. LONGEST PATH WITH FORBIDDEN PAIRS
    2. SHORTEST PATH WITH FORBIDDEN PAIRS
    3. MINIMUM POINT-TO-POINT CONNECTION
    4. MINIMUM METRIC DIMENSION
    5. MINIMUM TREE WIDTH
    6. MINIMUM GRAPH INFERENCE