File EasyCases.h

↰ Parent directory (ADS/complexity)

The polynomial halves of the pairs of Tabella 19.1 of the Conclusione, problems close to NP-hard ones but solvable in polynomial time, and the special cases that the Conclusione names, the interval graphs:

Definition (ADS/complexity/EasyCases.h)

Detailed Description

  • twoSat(), SODDISFATTIBILITA’ with at most two literals per clause, by the graph of the implications :math:` neg a Rightarrow b ` and :math:` neg b Rightarrow a ` of each clause :math:` a vee b `: the formula is satisfiable if and only if no variable is in the strongly connected component of its negation, and a variable is true if its component comes after that of its negation in topological order, O( n + m );

  • twoColoring(), the 2-COLORAZIONE, by a breadth first visit of each component, O( n^2 ) on the adjacency matrix;

  • bipartiteMatching(), the ABBINAMENTO 2-DIMENSIONALE, by a maximum flow from a source to the left nodes, along the edges, to a sink;

  • intervalGraph(), the graph whose nodes are intervals [ a , b ) and whose edges join those that intersect, and on it intervalClique(), the largest number of intervals through a point, by a sweep in :math:` O( n log n ) ; the independent set and the coloring of intervals are in :ref:`file_ADS_optimization_Intervals.h. The other easy halves are linearTiling() in File Domino.h (tested in chapter 18), eulerianCycle() in File EulerianCycle.h, fractionalKnapsack() in File FractionalKnapsack.h, kruskal() in File MinimumSpanningTree.h and shortestPaths() in File ShortestPaths.h.

The contracts [see File Contract.h]: the inputs are instances of the polynomial problems (clauses of at most two literals, unoriented graphs, intervals with a <= b) and each solution returned is checked as a postcondition. The operations are defined in EasyCases.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, Conclusione, https://algoritmicamente.it

  2. Aspvall, M. F. Plass, R. E. Tarjan, A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters 8(3), 121-123, 1979, doi:10.1016/0020-0190(79)90002-4

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions