|   | 
Details
   web
Records
Author (up) 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 2-12
Keywords Maximum edge biclique packing; Branch-and-price; 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 branch-and-price 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, F-69622 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000332427400002 Approved
Call Number UAI @ eduardo.moreno @ Serial 361
Permanent link to this record
 

 
Author (up) 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 10-11 Pages 1345-1355
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@ing-mat.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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000319029300005 Approved
Call Number UAI @ eduardo.moreno @ Serial 282
Permanent link to this record
 

 
Author (up) 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 65-80
Keywords Lifting; Shrinking; Precedence-constrained 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000361772500005 Approved
Call Number UAI @ eduardo.moreno @ Serial 525
Permanent link to this record
 

 
Author (up) Gaspers, S.; Liedloff, M.; Stein, M.; Suchan, K.
Title Complexity of splits reconstruction for low-degree trees Type
Year 2015 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 180 Issue Pages 89-100
Keywords Reconstruction of trees; Computational complexity; Computational chemistry
Abstract Given a vertex-weighted 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 NP-complete, 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 NP-complete when T is required to be a path, the problem is NP-complete when all vertices have unit weight and the maximum degree of T is required to be at most 3, and it remains NP-complete 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 fixed-parameter 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 physico-chemical 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000346545500009 Approved
Call Number UAI @ eduardo.moreno @ Serial 433
Permanent link to this record
 

 
Author (up) 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 7-8 Pages 1154-1161
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 k-vertex 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) 255-267] 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, PL-00325 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000317451700030 Approved
Call Number UAI @ eduardo.moreno @ Serial 276
Permanent link to this record
 

 
Author (up) Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K.
Title Minimum size tree-decompositions Type
Year 2018 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.
Volume 245 Issue Pages 109-127
Keywords Tree-decomposition; Treewidth; NP-hard
Abstract We study in this paper the problem of computing a tree-decomposition 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 tree-decomposition 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 NP-complete 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 2-connected 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000435046700011 Approved
Call Number UAI @ eduardo.moreno @ Serial 874
Permanent link to this record
 

 
Author (up) 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 259-266
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 #P-complete. 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 0166-218x ISBN Medium
Area Expedition Conference
Notes WOS:000299144900009 Approved
Call Number UAI @ eduardo.moreno @ Serial 190
Permanent link to this record