Records 
Author 
Acuna, V.; Ferreira, C.E.; Freire, A.S.; Moreno, E. 
Title 
Solving the maximum edge biclique packing problem on unbalanced bipartite graphs 
Type 

Year 
2014 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
164 
Issue 

Pages 
212 
Keywords 
Maximum edge biclique packing; Branchandprice; Metabolic networks; Product bundling 
Abstract 
A biclique is a complete bipartite graph. Given an (L, R)bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branchandprice scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved. 
Address 
[Acuna, V.] Univ Lyon 1, F69622 Villeurbanne, France, Email: afreire@ime.usp.br 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000332427400002 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
361 
Permanent link to this record 



Author 
Aracena, J.; Demongeot, J.; Fanchon, E.; Montalva, M. 
Title 
On the number of update digraphs and its relation with the feedback arc sets and tournaments 
Type 

Year 
2013 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
161 
Issue 
1011 
Pages 
13451355 
Keywords 
Update digraph; Feedback arc set; Tournament; Update schedule 
Abstract 
An update digraph corresponds to a labeled digraph that indicates a relative order of its nodes introduced to define equivalence classes of deterministic update schedules yielding the same dynamical behavior of a Boolean network. In Aracena et al. [1], the authors exhibited relationships between update digraphs and the feedback arc sets of a given digraph G. In this paper, we delve into the study of these relations. Specifically, we show differences and similarities between both sets through increasing and decreasing monotony properties in terms of their structural characteristics. Besides, we prove that these sets are equivalent if and only if all the digraph circuits are cycles. On the other hand, we characterize the minimal feedback arc sets of a given digraph in terms of their associated update digraphs. In particular, for complete digraphs, this characterization shows a close relation with acyclic tournaments. For the latter, we show that the size of the associated equivalence classes is a power of two. Finally, we determine exactly the number of update digraphs associated to digraphs containing a tournament. (C) 2013 Elsevier B.V. All rights reserved. 
Address 
Univ Concepcion, CI2 MA & Dept Ingn Matemat, Concepcion, Chile, Email: jaracena@ingmat.udec.cl; 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000319029300005 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
282 
Permanent link to this record 



Author 
Espinoza, D.; Goycoolea, M.; Moreno, E. 
Title 
The precedence constrained knapsack problem: Separating maximally violated inequalities 
Type 

Year 
2015 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
194 
Issue 

Pages 
6580 
Keywords 
Lifting; Shrinking; Precedenceconstrained knapsack problem; Induced cover inequality; Induced clique inequality; Separation problem 
Abstract 
We consider the problem of separating maximally violated inequalities for the precedence constrained knapsack problem. Though we consider maximally violated constraints in a very general way, special emphasis is placed on induced cover inequalities and induced clique inequalities. Our contributions include a new partial characterization of maximally violated inequalities, a new safe shrinking technique, and new insights on strengthening and lifting. This work follows on the work of Boyd (1993), Park and Park (1997), van de Leensel et al. (1999) and Boland et al. (2011). Computational experiments show that our new techniques and insights can be used to significantly improve the performance of cutting plane algorithms for this problem. (C) 2015 Elsevier B.V. All rights reserved. 
Address 
[Espinoza, Daniel] Univ Chile, Dept Ind Engn, Santiago, Chile, Email: daespino@dii.uchile.cl; 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000361772500005 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
525 
Permanent link to this record 



Author 
Feuilloley, L.; Fraigniaud, P.; Montealegre, P.; Rapaport, I.; Remila, E.; Todinca, I. 
Title 
Local certification of graphs with bounded genus 
Type 

Year 
2023 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
325 
Issue 

Pages 
936 
Keywords 
Distributed graph algorithms; Local certification; Prooflabeling scheme; Locally checkable proofs 
Abstract 
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as introduced by Kol, Oshman, and Saxena [PODC 2018]. In particular, by using this compiler, every lineartime algorithm for deciding the membership to some fixed graph class can be translated into a dMAM(O(log n)) protocol for this class, that is, a distributed interactive protocol with O(log n)bit proof size in nnode graphs, and three interactions between the (centralized) computationallyunbounded but nontrustable prover Merlin, and the (decentralized) randomized computationallylimited verifier Arthur. As a corollary, there is a dMAM(O(log n)) protocol for recognizing the class of planar graphs, as well as for recognizing the class of graphs with bounded genus.We show that there exists a distributed interactive protocol for recognizing the class of graphs with bounded genus performing just a single interaction, from the prover to the verifier, yet preserving proof size of O(log n) bits. This result also holds for the class of graphs with bounded nonorientable genus, that is, graphs that can be embedded on a nonorientable surface of bounded genus. The interactive protocols described in this paper are actually prooflabeling schemes, i.e., a subclass of interactive protocols, previously introduced by Korman, Kutten, and Peleg [PODC 2005]. In particular, these schn be computed a priori, at low cost, by the nodes themselves. Our results thus extend the recent prooflabeling scheme for planar graphs by Feuilloley et al. [PODC 2020], to graphs of bounded genus, and to graphs of bounded nonorientable genus. 
Address 

Corporate Author 

Thesis 

Publisher 

Place of Publication 

Editor 

Language 

Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218X 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000884423700002 
Approved 

Call Number 
UAI @ alexi.delcanto @ 
Serial 
1661 
Permanent link to this record 



Author 
Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K. 
Title 
Complexity of splits reconstruction for lowdegree trees 
Type 

Year 
2015 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
180 
Issue 

Pages 
89100 
Keywords 
Reconstruction of trees; Computational complexity; Computational chemistry 
Abstract 
Given a vertexweighted tree T, the split of an edge em T is the minimum over the weights of the two trees obtained by removing e from T, where the weight of a tree is the sum of weights of its vertices. Given a set of weighted vertices V and a multiset of integers s, we consider the problem of constructing a tree on V whose splits correspond to s. The problem is known to be NPcomplete, even when all vertices have unit weight and the maximum vertex degree of T is required to be at most 4. We show that the problem is strongly NPcomplete when T is required to be a path, the problem is NPcomplete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NPcomplete when all vertices have unit weight and T is required to be a caterpillar with unbounded hair length and maximum degree at most 3. We also design polynomial time algorithms for the variant where T is required to be a path and the number of distinct vertex weights is constant, and the variant where all vertices have unit weight and T has a constant number of leaves. The latter algorithm is not only polynomial when the number of leaves, k, is a constant, but also is a fixedparameter algorithm for parameter k. Finally, we shortly discuss the problem when the vertex weights are not given but can be freely chosen by an algorithm. The considered problem is related to building libraries of chemical compounds used for drug design and discovery. In these inverse problems, the goal is to generate chemical compounds having desired structural properties, as there is a strong relation between structural invariants of the particles, such as the Wiener index and, less directly, the problem under consideration here, and physicochemical properties of the substance. (C) 2014 Elsevier B.V. All rights reserved. 
Address 
[Gaspers, Serge] Univ New S Wales, Sch Comp Sci & Engn, Sydney, NSW 2052, Australia, Email: sergeg@cse.unsw.edu.au; 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000346545500009 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
433 
Permanent link to this record 



Author 
Kowalik, L.; Pilipczuk, M.; Suchan, K. 
Title 
Towards optimal kernel for connected vertex cover in planar graphs 
Type 

Year 
2013 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
161 
Issue 
78 
Pages 
11541161 
Keywords 
Kernelization; Planar graphs; Connected vertex cover 
Abstract 
We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does not admit a polynomial kernel for general graphs (unless NP subset of coNP/poly), for planar graphs Guo and Niedermeier [ICALP'08] showed a kernel with at most 14k vertices, subsequently improved by Wang et al. [MFCS'11] to 4k. The constant 4 here is so small that a natural question arises: could it be already an optimal value for this problem? In this paper we answer this question in the negative: we show a 11/3 kvertex kernel for CONNECTED VERTEX COVER in planar graphs. We believe that this result will motivate further study in the search for an optimal kernel. In our analysis, we show an extension of a theorem of Nishizeki and Baybars [Takao Nishizeki, Ilker Baybars, Lower bounds on the cardinality of the maximum matchings of planar graphs, Discrete Mathematics 28 (3) (1979) 255267] which might be of independent interest: every planar graph with n(>= 3) vertices of degree at least 3 contains a matching of cardinality at least n(>= 3)/3. (C) 2012 Elsevier B.V. All rights reserved. 
Address 
Univ Warsaw, Inst Informat, PL00325 Warsaw, Poland, Email: kowalik@mimuw.edu.pl; 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000317451700030 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
276 
Permanent link to this record 



Author 
Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K. 
Title 
Minimum size treedecompositions 
Type 

Year 
2018 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
245 
Issue 

Pages 
109127 
Keywords 
Treedecomposition; Treewidth; NPhard 
Abstract 
We study in this paper the problem of computing a treedecomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k >= 1, what is the complexity of computing a treedecomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NPcomplete for any fixed k >= 4 and polynomial for k <= 2; for k = 3, we show that it is polynomial in the class of trees and 2connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved. 
Address 
[Moataz, Fatima Zahra; Nisse, Nicolas] INRIA, Rennes, France, Email: nicolas.nisse@inria.fr 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000435046700011 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
874 
Permanent link to this record 



Author 
Ortiz, C.; Villanueva, M. 
Title 
Maximal independent sets in caterpillar graphs 
Type 

Year 
2012 
Publication 
Discrete Applied Mathematics 
Abbreviated Journal 
Discret Appl. Math. 
Volume 
160 
Issue 
3 
Pages 
259266 
Keywords 
Graph algorithms; Caterpillar graph; Enumeration of maximal independent sets; Intersection graph; Independent graph; Clique graph 
Abstract 
A caterpillar graph is a tree in which the removal of all pendant vertices results in a chordless path. In this work, we determine the number of maximal independent sets (mis) in caterpillar graphs. For a general graph, this problem is #Pcomplete. We provide a polynomial time algorithm to generate the whole family of mis in a caterpillar graph. We also characterize the independent graph (intersection graph of mis) and the clique graph (intersection graph of cliques) of complete caterpillar graphs. (C) 2011 Elsevier B.V. All rights reserved. 
Address 
[Villanueva, Monica] Univ Santiago Chile, Fac Engn, Santiago, Chile, Email: monica.villanueva@usach.cl 
Corporate Author 

Thesis 

Publisher 
Elsevier Science Bv 
Place of Publication 

Editor 

Language 
English 
Summary Language 

Original Title 

Series Editor 

Series Title 

Abbreviated Series Title 

Series Volume 

Series Issue 

Edition 

ISSN 
0166218x 
ISBN 

Medium 

Area 

Expedition 

Conference 

Notes 
WOS:000299144900009 
Approved 

Call Number 
UAI @ eduardo.moreno @ 
Serial 
190 
Permanent link to this record 