54 research outputs found
Reconstructing extended Petri nets with priorities - handling priority conflicts revisited
No full textThis work aims at reconstructing Petri net models for biological systems from experimental time-series data. The reconstructed models shall reproduce the experimentally observed dynamic behavior in a simulation. For that, we consider Petri nets with priority relations among the transitions and control-arcs, to obtain additional activation rules for transitions to control the dynamic behavior. An integrative reconstruction method, taking both priority relations and control-arcs into account, was proposed by Favre and Wagler in 2013. Here, we detail the aspect of choosing priorities and control-arcs such that dynamic conflicts can be resolved to finally arrive at the experimentally observed behavior
Characterizing N+-perfect line graphs
No full textThe aim of this paper is to study the Lovász-Schrijver PSD operator N+ applied to the edge relaxation of the stable set polytope of a graph. We are particularly interested in the problem of characterizing graphs for which N+ generates the stable set polytope in one step, called N+ -perfect graphs. It is conjectured that the only N+ -perfect graphs are those whose stable set polytope is described by inequalities with near-bipartite support. So far, this conjecture has been proved for near-perfect graphs, fs-perfect graphs, and webs. Here, we verify it for line graphs, by proving that in an N+ -perfect line graph the only facet-defining subgraphs are cliques and odd holes.Fil: Escalante, Mariana Silvina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; ArgentinaFil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; ArgentinaFil: Wagler, Annegret Katrin. Universite Blaise Pascal; Francia. Centre National de la Recherche Scientifique; Franci
Reconstructing extended Petri nets with priorities - handling priority conflicts revisited
No full textThis work aims at reconstructing Petri net models for biological systems from experimental time-series data. The reconstructed models shall reproduce the experimentally observed dynamic behavior in a simulation. For that, we consider Petri nets with priority relations among the transitions and control-arcs, to obtain additional activation rules for transitions to control the dynamic behavior. An integrative reconstruction method, taking both priority relations and control-arcs into account, was proposed by Favre and Wagler in 2013. Here, we detail the aspect of choosing priorities and control-arcs such that dynamic conflicts can be resolved to finally arrive at the experimentally observed behavior
Reconstructing extended Petri nets with priorities - handling priority conflicts revisited
No full textThis work aims at reconstructing Petri net models for biological systems from experimental time-series data. The reconstructed models shall reproduce the experimentally observed dynamic behavior in a simulation. For that, we consider Petri nets with priority relations among the transitions and control-arcs, to obtain additional activation rules for transitions to control the dynamic behavior. An integrative reconstruction method, taking both priority relations and control-arcs into account, was proposed by Favre and Wagler in 2013. Here, we detail the aspect of choosing priorities and control-arcs such that dynamic conflicts can be resolved to finally arrive at the experimentally observed behavior
Two new species of the genus Cylindrophis Wagler, 1828 (Squamata: Cylindrophiidae) from Southeast Asia
No full text© 2015 Amarasinghe et al. This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercialNoDerivatives 4.0 International License, which permits unrestricted use for non-commercial and education purposes only, in any medium, provided the original author and the official and authorized publication sources are recognized and properly credited. The official and authorized publication credit sources, which will be duly enforced, are as follows: official journal title Amphibian & Reptile Conservation; official journal website . The attached file is the published version of the article.NHM Repositor
Clique-perfectness and balancedness of some graph classes
No full textA graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Safe, Martin Dario. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; ArgentinaFil: Wagler, Annegret K.. Universite Blaise Pascal; Franci
Fleet Management for Autonomous Vehicles Using Multicommodity Coupled Flows in Time-Expanded Networks
No full textVIPAFLEET is a framework to develop models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). We consider a homogeneous fleet of such vehicles distributed at specified stations in a closed site to supply internal transportation, where the vehicles can be used in different modes of circulation (tram mode, elevator mode, taxi mode). We treat in this paper a variant of the Online Pickup-and-Delivery Problem related to the taxi mode by means of multicommodity coupled flows in a time-expanded network and propose a corresponding integer linear programming formulation. This enables us to compute optimal offline solutions. However, to apply the well-known meta-strategy Replan to the online situation by solving a sequence of offline subproblems, the computation times turned out to be too long, so that we devise a heuristic approach h-Replan based on the flow formulation. Finally, we evaluate the performance of h-Replan in comparison with the optimal offline solution, both in terms of competitive analysis and computational experiments, showing that h-Replan computes reasonable solutions, so that it suits for the online situation
Fleet management for autonomous vehicles: Online PDP under special constraints
No full textInternational audienceThe VIPAFLEET project consists in developing models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). Hereby, we consider a fleet of cars distributed at specified stations in an industrial area to supply internal transportation, where the cars can be used in different modes of circulation (tram mode, elevator mode, taxi mode). One goal is to develop and implement suitable algorithms for each mode in order to satisfy all the requests under an economic point of view by minimizing the total tour length. The innovative idea and challenge of the project is to develop and install a dynamic fleet management system that allows the operator to switch between the different modes within the different periods of the day according to the dynamic transportation demands of the users. We model the underlying online transportation system and propose a corresponding fleet management framework, to handle modes, demands and commands. We consider two modes of circulation, tram and elevator mode, propose for each mode appropriate on-line algorithms and evaluate their performance, both in terms of competitive analysis and practical behavior
Preprocessing for Network Reconstruction: Feasibility Test and Handling Infeasibility
No full textInternational audienceThe context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives tting the given data. For a successful reconstruction, the data need to satisfy two properties: re-producibility and monotonicity. In this paper, we focus on a necessary preprocessing step for a recent reconstruction approach. We test the data for reproducibility, provide a feasibility test to detect cases where the reconstruction from the given data may fail, and provide a strategy to cope with the infeasible cases. After having performed the preprocessing step, it is guaranteed that the (given or modied) data are appropriate as input for the main reconstruction algorithm
On superperfection of edge-intersection graphs of paths
No full textInternational audienceThe Routing and Spectrum Assignment problem in Flexgrid Elastic Optical Networks can be modeled in two phases: a selection of paths in the network and an interval coloring problem in the edge-intersection graph of these paths. The interval chromatic number equals the smallest size of a spectrum such that a proper interval coloring is possible, the weighted clique number is a natural lower bound. Graphs where both parameters coincide for all induced subgraphs and for all possible integral weights are called superperfect. We examine the question which minimal non-superperfect graphs can occur in the edge-intersection graphs of paths in different underlying networks and show that for any possible network (even if it is restricted to a path) the resulting edge-intersection graphs are not necessarily superperfect
- …
