Search

Your search keyword '"Sau, Ignasi"' showing total 368 results
Start Over Author "Sau, Ignasi"
368 results on '"Sau, Ignasi"'

351. A Polynomial-Time Algorithm for the Independent Set Problem in -Free Graphs

Author

Husić, Edin, Milanič, Martin, 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

Published
2019
Full Text
View/download PDF

352. Travelling on Graphs with Small Highway Dimension

Author

Disser, Yann, Feldmann, Andreas Emil, Klimm, Max, Könemann, Jochen, 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

Published
2019
Full Text
View/download PDF

353. Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth

Author

Dyer, Martin, Greenhill, Catherine, Müller, Haiko, 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

Published
2019
Full Text
View/download PDF

354. Classified Rank-Maximal Matchings and Popular Matchings – Algorithms and Hardness

Author

Nasre, Meghana, Nimbhorkar, Prajakta, Pulath, Nada, 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

Published
2019
Full Text
View/download PDF

355. Independent Set Reconfiguration Parameterized by Modular-Width

Author

Belmonte, Rémy, Hanaka, Tesshu, Lampis, Michael, Ono, Hirotaka, Otachi, Yota, 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

Published
2019
Full Text
View/download PDF

356. Intersection Graphs of Non-crossing Paths

Author

Chaplick, Steven, 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

Published
2019
Full Text
View/download PDF

357. Approximating Minimum Dominating Set on String Graphs

Author

Chakraborty, Dibyayan, Das, Sandip, Mukherjee, Joydeep, 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

Published
2019
Full Text
View/download PDF

358. Linear MIM-Width of Trees

Author

Høgemo, Svein, Telle, Jan Arne, Vågset, Erlend Raa, 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

Published
2019
Full Text
View/download PDF

359. 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

Published
2019
Full Text
View/download PDF

360. 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

Published
2019
Full Text
View/download PDF

361. 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

Published
2019
Full Text
View/download PDF

362. 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

Published
2019
Full Text
View/download PDF

363. 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

Published
2019
Full Text
View/download PDF

364. 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

Published
2019
Full Text
View/download PDF

365. 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

Published
2019
Full Text
View/download PDF

366. 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]

Published
2020
Full Text
View/download PDF

367. 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]

Published
2020
Full Text
View/download PDF

368. 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)

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.

Published
2011

Catalog

Books, media, physical & digital resources
See catalog results