363 results on '"Sau, Ignasi"'
Search Results
352. Geometric Representations of Dichotomous Ordinal Data
- Author
-
Angelini, Patrizio, Bekos, Michael A., Gronemann, Martin, Symvonis, Antonios, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
353. Subexponential Algorithms for Variants of Homomorphism Problem in String Graphs
- Author
-
Okrasa, Karolina, Rzążewski, Paweł, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
354. The Power of Cut-Based Parameters for Computing Edge Disjoint Paths
- Author
-
Ganian, Robert, Ordyniak, Sebastian, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
355. Graph Functionality
- Author
-
Alecu, Bogdan, Atminas, Aistis, Lozin, Vadim, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
356. On Happy Colorings, Cuts, and Structural Parameterizations
- Author
-
Bliznets, Ivan, Sagunov, Danil, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
357. Shortest Reconfiguration of Matchings
- Author
-
Bousquet, Nicolas, Hatanaka, Tatsuhiko, Ito, Takehiro, Mühlenthaler, Moritz, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
358. Flip Distances Between Graph Orientations
- Author
-
Aichholzer, Oswin, Cardinal, Jean, Huynh, Tony, Knauer, Kolja, Mütze, Torsten, Steiner, Raphael, Vogtenhuber, Birgit, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Sau, Ignasi, editor, and Thilikos, Dimitrios M., editor more...
- Published
- 2019
- Full Text
- View/download PDF
359. Dual Parameterization of Weighted Coloring.
- Author
-
Araújo, Júlio, Campos, Victor A., Lima, Carlos Vinícius G. C., dos Santos, Vinícius Fernandes, Sau, Ignasi, and Silva, Ana
- Subjects
- *
GRAPH coloring , *PARAMETERIZATION , *WEIGHTED graphs , *ALGORITHMS , *SCIENTIFIC computing , *TREE size - Abstract
Given a graph G, a properk-coloring of G is a partition c = (S i) i ∈ [ 1 , k ] of V(G) into k stable sets S 1 , ... , S k . Given a weight function w : V (G) → R + , the weight of a color S i is defined as w (i) = max v ∈ S i w (v) and the weight of a coloringc as w (c) = ∑ i = 1 k w (i) . Guan and Zhu (Inf Process Lett 61(2):77–81, 1997) defined the weighted chromatic number of a pair (G, w), denoted by σ (G , w) , as the minimum weight of a proper coloring of G. The problem of determining σ (G , w) has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on n-vertex trees in time n o (log n) unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. We focus on the so-called dual parameterization of the problem: given a vertex-weighted graph (G, w) and an integer k, is σ (G , w) ≤ ∑ v ∈ V (G) w (v) - k ? This parameterization has been recently considered by Escoffier (in: Proceedings of the 42nd international workshop on graph-theoretic concepts in computer science (WG). LNCS, vol 9941, pp 50–61, 2016), who provided an FPT algorithm running in time 2 O (k log k) · n O (1) , and asked which kernel size can be achieved for the problem. We provide an FPT algorithm in time 9 k · n O (1) , and prove that no algorithm in time 2 o (k) · n O (1) exists under the ETH. On the other hand, we present a kernel with at most (2 k - 1 + 1) (k - 1) vertices, and rule out the existence of polynomial kernels unless NP ⊆ coNP / poly , even on split graphs with only two different weights. Finally, we identify classes of graphs allowing for polynomial kernels, namely interval graphs, comparability graphs, and subclasses of circular-arc and split graphs, and in the latter case we present lower bounds on the degrees of the polynomials. [ABSTRACT FROM AUTHOR] more...
- Published
- 2020
- Full Text
- View/download PDF
360. On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths.
- Author
-
Araújo, Júlio, Campos, Victor A., Maia, Ana Karolinna, Sau, Ignasi, and Silva, Ana
- Subjects
- *
MATROIDS , *INTEGERS , *CODING theory - Abstract
For two positive integers k and ℓ , a (k × ℓ) -spindle is the union of k pairwise internally vertex-disjoint directed paths with ℓ arcs each between two vertices u and v. We are interested in the (parameterized) complexity of several problems consisting in deciding whether a given digraph contains a subdivision of a spindle, which generalize both the Maximum Flow and Longest Path problems. We obtain the following complexity dichotomy: for a fixed ℓ ≥ 1 , finding the largest k such that an input digraph G contains a subdivision of a (k × ℓ) -spindle is polynomial-time solvable if ℓ ≤ 3 , and NP-hard otherwise. We place special emphasis on finding spindles with exactly two paths and present FPT algorithms that are asymptotically optimal under the ETH. These algorithms are based on the technique of representative families in matroids, and use also color-coding as a subroutine. Finally, we study the case where the input graph is acyclic, and present several algorithmic and hardness results. [ABSTRACT FROM AUTHOR] more...
- Published
- 2020
- Full Text
- View/download PDF
361. On the (parameterized) complexity of recognizing well-covered (r,ℓ)-graph.
- Author
-
Alves, Sancrey Rodrigues, Dabrowski, Konrad K., Faria, Luerbio, Klein, Sulamita, Sau, Ignasi, and Souza, Uéverton S.
- Subjects
- *
PARAMETERIZATION , *GRAPH theory , *PARTITION functions , *GEOMETRIC vertices , *MATHEMATICAL complex analysis - Abstract
Abstract An (r , ℓ) - partition of a graph G is a partition of its vertex set into r independent sets and ℓ cliques. A graph is (r , ℓ) if it admits an (r , ℓ) -partition. A graph is well-covered if every maximal independent set is also maximum. A graph is (r , ℓ) - well-covered if it is both (r , ℓ) and well-covered. In this paper we consider two different decision problems. In the (r , ℓ) -Well-Covered Graph problem ((r , ℓ) wc-g for short), we are given a graph G , and the question is whether G is an (r , ℓ) -well-covered graph. In the Well-Covered (r , ℓ) -Graph problem (wc- (r , ℓ) g for short), we are given an (r , ℓ) -graph G together with an (r , ℓ) -partition, and the question is whether G is well-covered. This generates two infinite families of problems, for any fixed non-negative integers r and ℓ , which we classify as being P , coNP -complete, NP -complete, NP -hard, or coNP -hard. Only the cases wc- (r , 0) g for r ≥ 3 remain open. In addition, we consider the parameterized complexity of these problems for several choices of parameters, such as the size α of a maximum independent set of the input graph, its neighborhood diversity, its clique-width, or the number ℓ of cliques in an (r , ℓ) -partition. In particular, we show that the parameterized problem of determining whether every maximal independent set of an input graph G has cardinality equal to k can be reduced to the wc- (0 , ℓ) g problem parameterized by ℓ. In addition, we prove that both problems are coW[2] -hard but can be solved in XP -time. [ABSTRACT FROM AUTHOR] more...
- Published
- 2018
- Full Text
- View/download PDF
362. Faster parameterized algorithms for minor containment
- Author
-
Fedor V. Fomin, Frederic Dorn, Ignasi Sau, Isolde Adler, Dimitrios M. Thilikos, Sau, Ignasi, Department of Informatics [Bergen] (UiB), University of Bergen (UiB), Algorithmes, Graphes et Combinatoire (ALGCO), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Department of Informatics and Telecomunications [Kapodistrian Univ] (DI NKUA), and National and Kapodistrian University of Athens (NKUA) more...
- Subjects
Speedup ,General Computer Science ,Branch-decomposition ,Minor (linear algebra) ,0211 other engineering and technologies ,Parameterized complexity ,Graphs on surfaces ,Parameterized algorithms ,0102 computer and information sciences ,02 engineering and technology ,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] ,Dynamic programming ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Branchwidth ,0103 physical sciences ,Graph minor ,Graph minor containment ,010306 general physics ,Contraction (operator theory) ,Complement graph ,Forbidden graph characterization ,Mathematics ,Discrete mathematics ,Containment (computer programming) ,021103 operations research ,Graph minors ,16. Peace & justice ,Graph ,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] ,010201 computation theory & mathematics ,Bounded function ,Computer Science(all) - Abstract
International audience; The theory of Graph Minors by Robertson and Seymour is one of the deepest and significant theories in modern Combinatorics. This theory has also a strong impact on the recent development of Algorithms, and several areas, like Parameterized Complexity, have roots in Graph Minors. Until very recently it was a common belief that Graph Minors Theory is mainly of theoretical importance. However, it appears that many deep results from Robertson and Seymour's theory can be also used in the design of practical algorithms. Minor containment testing is one of algorithmically most important and technical parts of the theory, and minor containment in graphs of bounded branchwidth is a basic ingredient of this algorithm. In order to implement minor containment testing on graphs of bounded branchwidth, Hicks [NETWORKS 04] described an algorithm, that in time $\mathcal{O}(3^{k^2}\cdot (h+k-1)!\cdot m)$ decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. That algorithm follows the ideas introduced by Robertson and Seymour in [J'CTSB 95]. In this work we improve the dependence on k of Hicks' result by showing that checking if H is a minor of G can be done in time $\mathcal{O}(2^{(2k +1 )\cdot \log k} \cdot h^{2k} \cdot 2^{2h^2} \cdot m)$. Our approach is based on a combinatorial object called rooted packing, which captures the properties of the potential models of subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first single-exponential algorithm for minor containment testing. Namely, it runs in time $2^{\mathcal{O}(k)} \cdot h^{2k} \cdot 2^{\mathcal{O}(h)} \cdot n$, with n=|V(G)|. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction minor containment. more...
- Published
- 2011
363. On the parameterized complexity of the median and closest problems under some permutation metrics.
- Author
-
Cunha L, Sau I, and Souza U
- Abstract
Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. On the other hand, finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations of distinct integers, some distance metrics have been extensively studied. We investigate the median and closest problems on permutations over the following metrics: breakpoint distance, swap distance, block-interchange distance, short-block-move distance, and transposition distance. In biological applications some values are usually very small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation regarding some metrics of distance, even for only k = 3 permutations; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics when parameterized by the target distance d., Competing Interests: Declarations. Competing interests: The authors declare no competing interest., (© 2024. The Author(s).) more...
- Published
- 2024
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.