skip to main content

On disconnected cuts and separators

Ito, Takehiro ; Kamiński, Marcin ; Paulusma, Daniël ; Thilikos, Dimitrios M.

Discrete Applied Mathematics, 2011, Vol.159(13), pp.1345-1351 [Periódico revisado por pares]

Texto completo disponível

Ver todas as versões
Citações Citado por
  • Título:
    On disconnected cuts and separators
  • Autor: Ito, Takehiro ; Kamiński, Marcin ; Paulusma, Daniël ; Thilikos, Dimitrios M.
  • Assuntos: Cut Set ; 2 K 2 -Partition ; Retraction ; Compaction
  • É parte de: Discrete Applied Mathematics, 2011, Vol.159(13), pp.1345-1351
  • Descrição: For a connected graph G = ( V , E ) , a subset U ⊆ V is called a disconnected cut if U disconnects the graph, and the subgraph induced by U is disconnected as well. A natural condition is to impose that for any u ∈ U , the subgraph induced by ( V ∖ U ) ∪ { u } is connected. In that case, U is called a minimal disconnected cut. We show that the problem of testing whether a graph has a minimal disconnected cut is NP-complete. We also show that the problem of testing whether a graph has a disconnected cut separating two specified vertices, s and t , is NP-complete.
  • Idioma: Inglês

Buscando em bases de dados remotas. Favor aguardar.