Complexity of stability

DOI10.1016/j.jcss.2021.07.001zbMath1472.68113arXiv1910.00305OpenAlexW3183453945MaRDI QIDQ2237893

Jörg Rothe, Fabian Frei, Edith Hemaspaandra

Publication date: 28 October 2021

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.00305

zbMATH Keywords

stabilitycolorabilitysatisfiabilityvertex coverparallel access to NPdifference polynomial time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Stability, vertex stability, and unfrozenness for special graph classes

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
• Some simplified NP-complete graph problems
• 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
• Complexity of Stability.