Restricted vertex multicut on permutation graphs
Φόρτωση...
Ημερομηνία
Συγγραφείς
Papadopoulos, C.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Elsevier
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Discrete Applied Mathematics
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Given an undirected graph and pairs of terminals the Restricted Vertex Mul- ticut problem asks for a minimum set of nonterminal vertices whose removal disconnects each pair of terminals. The problem is known to be NP-complete for trees and polynomial-time solvable for interval graphs. In this paper we give a polynomial-time algorithm for the problem on permutation graphs. Furthermore we show that the problem remains NP-complete on split graphs whereas it becomes polynomial-time solvable for the class of co-bipartite graphs.
Περιγραφή
Λέξεις-κλειδιά
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών