Strongly chordal and chordal bipartite graphs are sandwich monotone
Φόρτωση...
Ημερομηνία
Συγγραφείς
Heggernes, P.
Mancini, F.
Papadopoulos, C.
Sritharan, R.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Springer Verlag (Germany)
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Journal of Combinatorial Optimization
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
A graph class is sandwich monotone if, for every pair of its graphs G (1)=(V,E (1)) and G (2)=(V,E (2)) with E (1)aS,E (2), there is an ordering e (1),aEuro broken vertical bar,e (k) of the edges in E (2)a-E (1) such that G=(V,E (1)a(a){e (1),aEuro broken vertical bar,e (i) }) belongs to the class for every i between 1 and k. In this paper we show that strongly chordal graphs and chordal bipartite graphs are sandwich monotone, answering an open question by Bakonyi and Bono (Czechoslov. Math. J. 46:577-583, 1997). So far, very few classes have been proved to be sandwich monotone, and the most famous of these are chordal graphs. Sandwich monotonicity of a graph class implies that minimal completions of arbitrary graphs into that class can be recognized and computed in polynomial time. For minimal completions into strongly chordal or chordal bipartite graphs no polynomial-time algorithm has been known. With our results such algorithms follow for both classes. In addition, from our results it follows that all strongly chordal graphs and all chordal bipartite graphs with edge constraints can be listed efficiently.
Περιγραφή
Λέξεις-κλειδιά
minimal completions, sandwich monotonicity, strongly chordal graphs, chordal bipartite graphs, minimum fill-in, completions, treewidth, separators, algorithms, complexity
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000294536500010
http://www.springerlink.com/content/6232678134j68v46/fulltext.pdf
http://www.springerlink.com/content/6232678134j68v46/fulltext.pdf
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών