Strongly chordal and chordal bipartite graphs are sandwich monotone

Pinar Heggernes (), Federico Mancini (), Charis Papadopoulos () and R. Sritharan ()
Additional contact information
Pinar Heggernes: University of Bergen
Federico Mancini: University of Bergen
Charis Papadopoulos: University of Ioannina
R. Sritharan: University of Dayton

Journal of Combinatorial Optimization, 2011, vol. 22, issue 3, No 10, 438-456

Abstract: Abstract 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⊂E 2, there is an ordering e 1,…,e k of the edges in E 2∖E 1 such that G=(V,E 1∪{e 1,…,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.

Keywords: Minimal completions; Sandwich monotonicity; Strongly chordal graphs; Chordal bipartite graphs (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9322-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:22:y:2011:i:3:d:10.1007_s10878-010-9322-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9322-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().