A New Graph Parameter to Measure Linearity
| Autor: | Reza Naserasr, Michel Habib, Lalla Mouatadid, Pierre Charbit |
|---|---|
| Přispěvatelé: | Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Computer Science [University of Toronto] (DCS), University of Toronto |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Sequence Mathematical optimization Conjecture 010102 general mathematics [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Sigma 0102 computer and information sciences 01 natural sciences Combinatorics Lexicographic breadth-first search 010201 computation theory & mathematics Chordal graph Computer Science - Data Structures and Algorithms Discrete Mathematics and Combinatorics Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Linear complex structure Geometry and Topology 0101 mathematics Graph property Time complexity Mathematics |
| Zdroj: | LNCS COCOA 2017-11th Annual International Conference on Combinatorial Optimization and Applications COCOA 2017-11th Annual International Conference on Combinatorial Optimization and Applications, Dec 2017, Shanghai, China. pp.154-168, ⟨10.1007/978-3-319-71147-8_11⟩ Combinatorial Optimization and Applications ISBN: 9783319711461 COCOA (2) |
| DOI: | 10.1007/978-3-319-71147-8_11⟩ |
| Popis: | Since its introduction to recognize chordal graphs by Rose, Tarjan, and Lueker, Lexicographic Breadth First Search (LexBFS) has been used to come up with simple, often linear time, algorithms on various classes of graphs. These algorithms are usually multi-sweep algorithms; that is they compute LexBFS orderings \(\sigma _1, \ldots , \sigma _k\), where \(\sigma _i\) is used to break ties for \(\sigma _{i+1}\). Since the number of LexBFS orderings for a graph is finite, this infinite sequence \(\{\sigma _i\}\) must have a loop, i.e. a multi-sweep algorithm will loop back to compute \(\sigma _j\), for some j. We study this new graph invariant, LexCycle(G), defined as the maximum length of a cycle of vertex orderings obtained via a sequence of LexBFS\(^+\). In this work, we focus on graph classes with small LexCycle. We give evidence that a small LexCycle often leads to linear structure that has been exploited algorithmically on a number of graph classes. In particular, we show that for proper interval, interval, co-bipartite, domino-free cocomparability graphs, as well as trees, there exists two orderings \(\sigma \) and \(\tau \) such that \(\sigma = \text {LexBFS}^+(\tau )\) and \(\tau = \text {LexBFS}^+(\sigma )\). One of the consequences of these results is the simplest algorithm to compute a transitive orientation for these graph classes. It was conjectured by Stacho [2015] that LexCycle is at most the asteroidal number of the graph class, we disprove this conjecture by giving a construction for which \({{\mathrm{LexCycle}}}(G) > an(G)\), the asteroidal number of G. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|