• DocumentCode
    3394782
  • Title

    3-coloring in time 0(1.3446n): a no-MIS algorithm

  • Author

    Beigel, Richard ; Eppstein, David

  • Author_Institution
    Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
  • fYear
    1995
  • fDate
    23-25 Oct 1995
  • Firstpage
    444
  • Lastpage
    452
  • Abstract
    We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2,3)-SSS while the other problems above are special cases of (3,2)-SSS; there is also a natural duality transformation from (a,b)-SSS to (b,a)-SSS. We give a fast algorithm for (3,2)-SSS and use it to improve the time bounds for solving the other problems listed above
  • Keywords
    computability; computational complexity; decidability; duality (mathematics); graph colouring; 3-SAT; 3-coloring; 3-edge-coloring; 3-list-coloring; NP-complete problems; common generalization; duality transformation; symbol-system satisfiability; time bounds; worst case time bounds; Computer science; NP-complete problem; Polynomials; Search problems; Testing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on
  • Conference_Location
    Milwaukee, WI
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-7183-1
  • Type

    conf

  • DOI
    10.1109/SFCS.1995.492575
  • Filename
    492575
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3394782