Idioma:

On disconnected cuts and separators

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

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

Kidlington: Elsevier B.V

Texto completo disponível

Citações Citado por

Enviar para

Título:
On disconnected cuts and separators
Autor: Ito, Takehiro ; Kamiński, Marcin ; Paulusma, Daniël ; Thilikos, Dimitrios M.
Assuntos: [formula omitted]-partition ; Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Combinatorics ; Combinatorics. Ordered structures ; Compaction ; Computer science; control theory; systems ; Cut set ; Disengaging ; Exact sciences and technology ; General topology ; Graphs ; Information retrieval. Graph ; Mathematical analysis ; Mathematics ; Retraction ; Sciences and techniques of general use ; Separators ; Theoretical computing ; Topology. Manifolds and cell complexes. Global analysis and analysis on manifolds
É parte de: Discrete Applied Mathematics, 2011-08, Vol.159 (13), p.1345-1351
Notas: ObjectType-Article-2
SourceType-Scholarly Journals-1
ObjectType-Feature-1
content type line 23
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.
Editor: Kidlington: Elsevier B.V
Idioma: Inglês

Links

View record in Pascal Francis

Voltar para lista de resultados

Realização: Logos de Redes Sociais:

On disconnected cuts and separators

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

Kidlington: Elsevier B.V

Buscando em bases de dados remotas. Favor aguardar.