Stability, vertex stability, and unfrozenness for special graph classes

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP
The behavior of clique-width under graph operations and graph transformations
The strong exponential hierarchy collapses
Computing a maximum cardinality matching in a bipartite graph in time $O(n^{1,5}\sqrt{m/\log \,n})$
The complexity of Kemeny elections
The complexity of facets (and some facets of complexity)
More complicated questions about maxima and minima, and some closures of NP
Complement reducible graphs
A partial k-arboretum of graphs with bounded treewidth
Exact complexity of the winner problem for Young elections
Default reasoning from conditional knowledge bases: Complexity and tractable cases
Edge dominating set and colorings on graphs with fixed clique-width
Linear time solvable optimization problems on graphs of bounded clique-width
Upper bounds to the clique width of graphs
Complexity of stability
A novel characterization of the complexity class $\Theta_k^{\mathrm{P}}$ based on counting and comparison
Complexity theory and cryptology. An introduction to cryptocomplexity.
Approximating clique-width and branch-width
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
Bounded Query Classes
Clique-Width is NP-Complete
A Linear Recognition Algorithm for Cographs
Graph minors. II. Algorithmic aspects of tree-width
Complexity of Finding Embeddings in a k-Tree
Exact analysis of Dodgson elections
NP trees and Carnap's modal logic
Bounds on the Cost of Stabilizing a Cooperative Game
The Minimization Problem for Boolean Formulas
Approximating rank-width and clique-width quickly
On the Relationship Between Clique-Width and Treewidth
Parameterized Algorithms
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
LATIN 2004: Theoretical Informatics

This page was built for publication: Stability, vertex stability, and unfrozenness for special graph classes