A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP (Q494789): Difference between revisions

From MaRDI portal
Importer (talk | contribs)
Changed an Item
Normalize DOI.
 
(7 intermediate revisions by 6 users not shown)
Property / DOI
 
Property / DOI: 10.1007/s00453-014-9883-7 / rank
Normal rank
 
Property / author
 
Property / author: Keith J. Edwards / rank
Normal rank
 
Property / author
 
Property / author: Eric J. McDermid / rank
Normal rank
 
Property / author
 
Property / author: Keith J. Edwards / rank
 
Normal rank
Property / author
 
Property / author: Eric J. McDermid / rank
 
Normal rank
Property / describes a project that uses
 
Property / describes a project that uses: MAX-2-SAT / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2074729689 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Forbidden minors characterization of partial 3-trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4511230 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A partial k-arboretum of graphs with bounded treewidth / rank
 
Normal rank
Property / cites work
 
Property / cites work: Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3043707 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An exact algorithm for MAX-CUT in sparse graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fragmentability of graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Improved upper bounds for planarization and series-parallelization of degree-bounded graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2911581 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On two techniques of combining branching and treewidth / rank
 
Normal rank
Property / cites work
 
Property / cites work: A measure & conquer approach for the analysis of exact algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Pathwidth of cubic graphs and exact algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact exponential algorithms. / rank
 
Normal rank
Property / cites work
 
Property / cites work: A universally fastest algorithm for Max 2-sat, Max 2-CSP, and everything in between / rank
 
Normal rank
Property / cites work
 
Property / cites work: New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree / rank
 
Normal rank
Property / cites work
 
Property / cites work: New exact algorithms for the 2-constraint satisfaction problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Maximum acyclic and fragmented sets in regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4501522 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new approach to proving upper bounds for MAX-2-SAT / rank
 
Normal rank
Property / cites work
 
Property / cites work: New Bounds for MAX-SAT by Clause Learning / rank
 
Normal rank
Property / cites work
 
Property / cites work: New Upper Bounds for Maximum Satisfiability / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach / rank
 
Normal rank
Property / cites work
 
Property / cites work: Linear-programming design and analysis of fast algorithms for Max 2-CSP / rank
 
Normal rank
Property / cites work
 
Property / cites work: Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function / rank
 
Normal rank
Property / cites work
 
Property / cites work: Automata, Languages and Programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4414647 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Open problems around exact algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact Algorithms for Maximum Independent Set / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1007/S00453-014-9883-7 / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 19:23, 9 December 2024

scientific article
Language Label Description Also known as
English
A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
scientific article

    Statements

    A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP (English)
    0 references
    0 references
    2 September 2015
    0 references
    constraint satisfaction problems
    0 references
    Max 2-CSP
    0 references
    treewidth
    0 references
    pathwidth
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references