11 Search Results for "Silva, Ana"

Document
DOI: 10.4230/LIPIcs.SAND.2023.1
Snapshot Disjointness in Temporal Graphs

Authors: Allen Ibiapina and Ana Silva

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness have been proposed over the years, and the validity of Menger’s Theorem, as well as the complexity of related problems, has been investigated. Menger’s Theorem states that the maximum number of disjoint paths between two vertices is equal to the minimum number of vertices required to disconnect them. In this paper, we introduce and investigate a type of disjointness that is only time dependent. Two walks are said to be snapshot disjoint if they are not active in a same snapshot (also called timestep). The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the size of the solution. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg and Kumar in their seminal paper (STOC'2000), we define a Mengerian graph for time as a graph G for which there is no time labeling for its edges where Menger’s Theorem does not hold in the context of snapshot disjointness. We then give a characterization of Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. Finally, we also prove that, given a temporal graph (G,λ) and a pair of vertices s,z ∈ V(G), deciding whether at most h multiedges can separate s from z is NP-complete, where one multiedge uv is the set of all edges with endpoints u and v.
Cite as

Allen Ibiapina and Ana Silva. Snapshot Disjointness in Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ibiapina_et_al:LIPIcs.SAND.2023.1,
  author =	{Ibiapina, Allen and Silva, Ana},
  title =	{{Snapshot Disjointness in Temporal Graphs}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.1},
  URN =		{urn:nbn:de:0030-drops-179379},
  doi =		{10.4230/LIPIcs.SAND.2023.1},
  annote =	{Keywords: Temporal graphs, Menger’s Theorem, Snapshot disjointness}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2022.4
Introductory Programming in Higher Education: A Systematic Literature Review

Authors: Gabryella Rodrigues, Ana Francisca Monteiro, and António Osório

Published in: OASIcs, Volume 102, Third International Computer Programming Education Conference (ICPEC 2022)

Abstract
A systematic literature review was performed on 33 papers obtained from the ACM, IEEE and Sciencedirect databases, in order to understand in depth, the introductory programming discipline (CS1) in higher education. Recently published works have been covered, providing an overview of the teaching-learning process of introductory programming and enabling to find out whether the research developed by universities worldwide is in line with the proposals made by ACM/IEEE-CS group for computer courses, regarding the transition to the competency-based model. The results show that the new techniques/technologies currently used in software development, as an example of agile methodology, has influenced the teaching-learning process of CS1 together with methods such as visual programming and e-learning. The analyzed papers discuss the importance of developing not only technical, but also social skills, corroborating that methodologies used in introductory programming courses need to focus on preparing students for an increasingly competitive market, associating new skills with technical aspects.
Cite as

Gabryella Rodrigues, Ana Francisca Monteiro, and António Osório. Introductory Programming in Higher Education: A Systematic Literature Review. In Third International Computer Programming Education Conference (ICPEC 2022). Open Access Series in Informatics (OASIcs), Volume 102, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rodrigues_et_al:OASIcs.ICPEC.2022.4,
  author =	{Rodrigues, Gabryella and Monteiro, Ana Francisca and Os\'{o}rio, Ant\'{o}nio},
  title =	{{Introductory Programming in Higher Education: A Systematic Literature Review}},
  booktitle =	{Third International Computer Programming Education Conference (ICPEC 2022)},
  pages =	{4:1--4:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-229-7},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{102},
  editor =	{Sim\~{o}es, Alberto and Silva, Jo\~{a}o Carlos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2022.4},
  URN =		{urn:nbn:de:0030-drops-166085},
  doi =		{10.4230/OASIcs.ICPEC.2022.4},
  annote =	{Keywords: systematic literature review, CS1, introductory programming, teaching programming, learning programming}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2022.5
Feedback Systems for Students Solving Problems Related to Polynomials of Degree Two or Lower

Authors: Luke Adrian Gubbins Bayzid, Ana Maria Reis D'Azevedo Breda, Eugénio Alexandre Miguel Rocha, and José Manuel Dos Santos Dos Santos

Published in: OASIcs, Volume 102, Third International Computer Programming Education Conference (ICPEC 2022)

Abstract
In this paper, we present the first attempts to design and implement an algorithm that effectively responds to errors in a student’s resolution in problems related to polynomials of degree two or lower. The algorithm analyzes the student’s input by comparing pre-established resolution patterns. The obtained results of the implementation show that the algorithm is effective at the classes of problems created within the project’s scope. Future work will concern the expansion of the number of classes to other common types of problems, such as higher-degree polynomials, and its use at a large scale using open-source software with CAS capabilities.
Cite as

Luke Adrian Gubbins Bayzid, Ana Maria Reis D'Azevedo Breda, Eugénio Alexandre Miguel Rocha, and José Manuel Dos Santos Dos Santos. Feedback Systems for Students Solving Problems Related to Polynomials of Degree Two or Lower. In Third International Computer Programming Education Conference (ICPEC 2022). Open Access Series in Informatics (OASIcs), Volume 102, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bayzid_et_al:OASIcs.ICPEC.2022.5,
  author =	{Bayzid, Luke Adrian Gubbins and Breda, Ana Maria Reis D'Azevedo and Rocha, Eug\'{e}nio Alexandre Miguel and Dos Santos, Jos\'{e} Manuel Dos Santos},
  title =	{{Feedback Systems for Students Solving Problems Related to Polynomials of Degree Two or Lower}},
  booktitle =	{Third International Computer Programming Education Conference (ICPEC 2022)},
  pages =	{5:1--5:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-229-7},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{102},
  editor =	{Sim\~{o}es, Alberto and Silva, Jo\~{a}o Carlos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2022.5},
  URN =		{urn:nbn:de:0030-drops-166094},
  doi =		{10.4230/OASIcs.ICPEC.2022.5},
  annote =	{Keywords: Automatic feedback, Algorithms, Algebraic systems}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.11
Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases ((Co)algebraic pearls)

Authors: Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
We prove that every finitely generated convex set of finitely supported probability distributions has a unique base. We apply this result to provide an alternative proof of a recent result: the algebraic theory of convex semilattices presents the monad of convex sets of probability distributions.
Cite as

Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli. Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CALCO.2021.11,
  author =	{Bonchi, Filippo and Sokolova, Ana and Vignudelli, Valeria},
  title =	{{Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.11},
  URN =		{urn:nbn:de:0030-drops-153666},
  doi =		{10.4230/LIPIcs.CALCO.2021.11},
  annote =	{Keywords: Convex sets of distributions monad, Convex semilattices, Unique base}
}
Document
(Co)algebraic pearls
DOI: 10.4230/LIPIcs.CALCO.2021.23
Nawrotzki’s Algorithm for the Countable Splitting Lemma, Constructively ((Co)algebraic pearls)

Authors: Ana Sokolova and Harald Woracek

Published in: LIPIcs, Volume 211, 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)

Abstract
We reprove the countable splitting lemma by adapting Nawrotzki’s algorithm which produces a sequence that converges to a solution. Our algorithm combines Nawrotzki’s approach with taking finite cuts. It is constructive in the sense that each term of the iteratively built approximating sequence as well as the error between the approximants and the solution is computable with finitely many algebraic operations.
Cite as

Ana Sokolova and Harald Woracek. Nawrotzki’s Algorithm for the Countable Splitting Lemma, Constructively ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sokolova_et_al:LIPIcs.CALCO.2021.23,
  author =	{Sokolova, Ana and Woracek, Harald},
  title =	{{Nawrotzki’s Algorithm for the Countable Splitting Lemma, Constructively}},
  booktitle =	{9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-212-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{211},
  editor =	{Gadducci, Fabio and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2021.23},
  URN =		{urn:nbn:de:0030-drops-153781},
  doi =		{10.4230/LIPIcs.CALCO.2021.23},
  annote =	{Keywords: countable splitting lemma, distributions with given marginals, couplings}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2021.12
A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals

Authors: Marco Silva, João Pedro Pedroso, Ana Viana, and Xenia Klimentova

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We study last-mile delivery with the option of crowd shipping, where a company makes use of occasional drivers to complement its vehicle’s fleet in the activity of delivering products to its customers. We model it as a data-driven distributionally robust optimization approach to the capacitated vehicle routing problem. We assume the marginals of the defined uncertainty vector are known, but the joint distribution is difficult to estimate. The presence of customers and available occasional drivers can be random. We adopt a strategic planning perspective, where an optimal a priori solution is calculated before the uncertainty is revealed. Therefore, without the need for online resolution performance, we can experiment with exact solutions. Solving the problem defined above is challenging: not only the first-stage problem is already NP-Hard, but also the uncertainty and potentially the second-stage decisions are binary of high dimension, leading to non-convex optimization formulations that are complex to solve. We propose a branch-price-and-cut algorithm taking into consideration measures that exploit the intrinsic characteristics of our problem and reduce the complexity to solve it.
Cite as

Marco Silva, João Pedro Pedroso, Ana Viana, and Xenia Klimentova. A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{silva_et_al:OASIcs.ATMOS.2021.12,
  author =	{Silva, Marco and Pedroso, Jo\~{a}o Pedro and Viana, Ana and Klimentova, Xenia},
  title =	{{A Branch-Price-And-Cut Algorithm for Stochastic Crowd Shipping Last-Mile Delivery with Correlated Marginals}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{12:1--12:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.12},
  URN =		{urn:nbn:de:0030-drops-148811},
  doi =		{10.4230/OASIcs.ATMOS.2021.12},
  annote =	{Keywords: Last-mile delivery, Stochastic Vehicle Routing Problem, Crowd shipping, Distributionally Robust Optimization, Data-driven Optimization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.38
Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete

Authors: Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira, and Ana Silva

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80’s, being one of the problems proposed by Johnson on his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still not known. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4.
Cite as

Celina M. H. de Figueiredo, Alexsander A. de Melo, Fabiano S. Oliveira, and Ana Silva. Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{defigueiredo_et_al:LIPIcs.MFCS.2021.38,
  author =	{de Figueiredo, Celina M. H. and de Melo, Alexsander A. and Oliveira, Fabiano S. and Silva, Ana},
  title =	{{Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.38},
  URN =		{urn:nbn:de:0030-drops-144781},
  doi =		{10.4230/LIPIcs.MFCS.2021.38},
  annote =	{Keywords: maximum cut, interval graphs, interval lengths, interval count, NP-complete}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2020.2
Challenges and Solutions from an Embedded Programming Bootcamp

Authors: J. Pedro Amaro, Jorge Barreiros, Fernanda Coutinho, João Durães, Frederico Santos, Ana Alves, Marco Silva, and João Cunha

Published in: OASIcs, Volume 81, First International Computer Programming Education Conference (ICPEC 2020)

Abstract
Due to the proliferation of IT companies developing web and mobile applications, computer programmers are in such high demand that universities can’t satisfy it with newly graduated students. In response, some organisations started to create coding bootcamps, providing intensive full-time courses focused on unemployed people or individuals seeking for a career change. There is, however, a different set of skills that is becoming increasingly required, but is not addressed by those courses: embedded programming. In fact, the Internet of Things is connecting every device to the internet, thus making knowledge on hardware and C/C++ programming very relevant skills. A group of computer science and electrical engineering university teachers, in collaboration with several industry stakeholders, have promoted an embedded systems programming course in C and C++. This course is based on an intensive project-based approach comprising 6 months of daylong classes followed by 9 months of paid internships. After two editions, thirty embedded programmers, with no relevant previous programming experience, have been placed with the partners’ working force. In this paper, the course organisation and pedagogical methodologies are described. Problems, challenges and adopted solutions are presented and analysed. We conclude that in spite of the intense rhythm and demanding nature of the subject matter, it is possible to find the structure and solutions that keep students engaged and motivated throughout the course, allowing them to gain the required competences and successfully transition into a new career path.
Cite as

J. Pedro Amaro, Jorge Barreiros, Fernanda Coutinho, João Durães, Frederico Santos, Ana Alves, Marco Silva, and João Cunha. Challenges and Solutions from an Embedded Programming Bootcamp. In First International Computer Programming Education Conference (ICPEC 2020). Open Access Series in Informatics (OASIcs), Volume 81, pp. 2:1-2:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{amaro_et_al:OASIcs.ICPEC.2020.2,
  author =	{Amaro, J. Pedro and Barreiros, Jorge and Coutinho, Fernanda and Dur\~{a}es, Jo\~{a}o and Santos, Frederico and Alves, Ana and Silva, Marco and Cunha, Jo\~{a}o},
  title =	{{Challenges and Solutions from an Embedded Programming Bootcamp}},
  booktitle =	{First International Computer Programming Education Conference (ICPEC 2020)},
  pages =	{2:1--2:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-153-5},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{81},
  editor =	{Queir\'{o}s, Ricardo and Portela, Filipe and Pinto, M\'{a}rio and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2020.2},
  URN =		{urn:nbn:de:0030-drops-122896},
  doi =		{10.4230/OASIcs.ICPEC.2020.2},
  annote =	{Keywords: Coding Bootcamp, Embedded Programming, Career Change}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.6
Tree Automata as Algebras: Minimisation and Determinisation

Authors: Gerco van Heerdt, Tobias Kappé, Jurriaan Rot, Matteo Sammartino, and Alexandra Silva

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
We study a categorical generalisation of tree automata, as algebras for a fixed endofunctor endowed with initial and final states. Under mild assumptions about the base category, we present a general minimisation algorithm for these automata. We then build upon and extend an existing generalisation of the Nerode equivalence to a categorical setting and relate it to the existence of minimal automata. Finally, we show that generalised types of side-effects, such as non-determinism, can be captured by this categorical framework, leading to a general determinisation procedure.
Cite as

Gerco van Heerdt, Tobias Kappé, Jurriaan Rot, Matteo Sammartino, and Alexandra Silva. Tree Automata as Algebras: Minimisation and Determinisation. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vanheerdt_et_al:LIPIcs.CALCO.2019.6,
  author =	{van Heerdt, Gerco and Kapp\'{e}, Tobias and Rot, Jurriaan and Sammartino, Matteo and Silva, Alexandra},
  title =	{{Tree Automata as Algebras: Minimisation and Determinisation}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.6},
  URN =		{urn:nbn:de:0030-drops-114341},
  doi =		{10.4230/LIPIcs.CALCO.2019.6},
  annote =	{Keywords: tree automata, algebras, minimisation, determinisation, Nerode equivalence}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2018.12
Dual Parameterization of Weighted Coloring

Authors: Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract
Given a graph G, a proper k-coloring of G is a partition c = (S_i)_{i in [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 in S_i} w(v) and the weight of a coloring c as w(c) = sum_{i=1}^{k} w(i). Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair (G,w), denoted by sigma(G,w), as the minimum weight of a proper coloring of G. The problem of determining sigma(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 sigma(G,w) <= sum_{v in V(G)} w(v) - k? This parameterization has been recently considered by Escoffier [WG, 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 running 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 subseteq coNP/poly, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.
Cite as

Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, and Ana Silva. Dual Parameterization of Weighted Coloring. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{araujo_et_al:LIPIcs.IPEC.2018.12,
  author =	{Ara\'{u}jo, J\'{u}lio and Campos, Victor A. and Lima, Carlos Vin{\'\i}cius G. C. and Fernandes dos Santos, Vin{\'\i}cius and Sau, Ignasi and Silva, Ana},
  title =	{{Dual Parameterization of Weighted Coloring}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.12},
  URN =		{urn:nbn:de:0030-drops-102134},
  doi =		{10.4230/LIPIcs.IPEC.2018.12},
  annote =	{Keywords: weighted coloring, max coloring, parameterized complexity, dual parameterization, FPT algorithms, polynomial kernels, split graphs, interval graphs}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2017.23
The Power of Convex Algebras

Authors: Filippo Bonchi, Alexandra Silva, and Ana Sokolova

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
Probabilistic automata (PA) combine probability and nondeterminism. They can be given different semantics, like strong bisimilarity, convex bisimilarity, or (more recently) distribution bisimilarity. The latter is based on the view of PA as transformers of probability distributions, also called belief states, and promotes distributions to first-class citizens. We give a coalgebraic account of the latter semantics, and explain the genesis of the belief-state transformer from a PA. To do so, we make explicit the convex algebraic structure present in PA and identify belief-state transformers as transition systems with state space that carries a convex algebra. As a consequence of our abstract approach, we can give a sound proof technique which we call bisimulation up-to convex hull.
Cite as

Filippo Bonchi, Alexandra Silva, and Ana Sokolova. The Power of Convex Algebras. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bonchi_et_al:LIPIcs.CONCUR.2017.23,
  author =	{Bonchi, Filippo and Silva, Alexandra and Sokolova, Ana},
  title =	{{The Power of Convex Algebras}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.23},
  URN =		{urn:nbn:de:0030-drops-77966},
  doi =		{10.4230/LIPIcs.CONCUR.2017.23},
  annote =	{Keywords: belief-state transformers, bisimulation up-to, coalgebra, convex algebra, convex powerset monad, probabilistic automata}
}
  • Refine by Author
  • 3 Silva, Ana
  • 3 Sokolova, Ana
  • 2 Bonchi, Filippo
  • 2 Silva, Alexandra
  • 2 Silva, Marco
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Transportation
  • 1 Computing methodologies
  • 1 General and reference → Surveys and overviews
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Combinatorics
  • Show More...

  • Refine by Keyword
  • 2 interval graphs
  • 1 Algebraic systems
  • 1 Algorithms
  • 1 Automatic feedback
  • 1 CS1
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 4 2021
  • 2 2019
  • 2 2022
  • 1 2017
  • 1 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact