Complexity of Stability.

DOI10.4230/lipics.isaac.2020.19OpenAlexW3117210581MaRDI QIDQ6065416

Jörg Rothe, Edith Hemaspaandra, Fabian Frei

Publication date: 14 November 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.19

zbMATH Keywords

criticalitycomplexitystabilityrobustnessindependent setcolorabilitycliquesatisfiabilityvertex coverparallel access to NPDPlocal modificationscodpunfrozenness

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Complexity of stability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• Domination alteration sets in graphs
• Total domination critical and stable graphs upon edge removal
• Extremal graphs domination insensitive to the removal of \(k\) edges
• Graphs whose vertex independence number is unaffected by single edge addition or deletion
• The complexity of Kemeny elections
• Exact complexity of exact-four-colorability
• The complexity of facets (and some facets of complexity)
• More complicated questions about maxima and minima, and some closures of NP
• The complexity of facets resolved
• Role colouring a graph
• Exact complexity of the winner problem for Young elections
• Total domination stability in graphs
• Structural properties of edge-chromatic critical multigraphs
• On the complexity of unfrozen problems
• The complexity of online manipulation of sequential elections
• Core Stability in Hedonic Coalition Formation
• Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-Complete
• Bounded Query Classes
• A graph coloring algorithm for large scheduling problems
• Anticritical graphs
• Exact analysis of Dodgson elections
• On computing Boolean connectives of characteristic functions
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• Finding Optimal Solutions With Neighborly Help.
• Determining computational complexity from characteristic ‘phase transitions’
• Some Theorems on Abstract Graphs

This page was built for publication: Complexity of Stability.