NSTL国家科技图书文献中心

1. Bridging the Gap Between Single and Multi Objective Games NSTL国家科技图书文献中心

Willem Ropke | Carla Groenland ... - 《International Conference on Autonomous Agents and Multiagent Systems: AAMAS 2023, London, UK, 29 May - 2 June 2023, volume 1 of 4》 - International Conference on Autonomous Agents and Multiagent Systems - 2023, - 224～232 - 共9页

摘要：A classic model to study strategic decision making in multi-agent systems is the normal-form game. This model can be generalised to allow for an infinite number of pure strategies leading to continuou...

关键词： Game theory | Continuous game | Multi-objective | Nash equilibria

2. Reconstructing Graphs from Connected Triples NSTL国家科技图书文献中心

Paul Bastide | Linda Cook ... - 《Graph-Theoretic Concepts in Computer Science: 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28-30, 2023, Revised Selected Papers》 - International Workshop on Graph-Theoretic Concepts in Computer Science - 2023, - 16～29 - 共14页

摘要：We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different ...

关键词： Algorithms | Graph reconstruction | Indeterminacy | Uncertainty | Connected subgraphs

3. Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space NSTL国家科技图书文献中心

Hans L. Bodlaender | Carla Groenland ... - 《IEEE 62nd Annual Symposium on Foundations of Computer Science: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 7-10 Feb. 2022, Virtual Conference, Denver, CO, USA》 - IEEE Annual Symposium on Foundations of Computer Science - 2022, - 193～204 - 共12页

摘要：Let XNLP be the class of parameterized prob-lems such that an instance of size $n$ with parameter...

关键词： Computer science | Processor scheduling | Bandwidth | Complexity theory

4. The Curse of Ties in Congestion Games with Limited Lookahead NSTL国家科技图书文献中心

Carla Groenland | Guido Schafer - 《17th International Conference on Autonomous Agents and Multiagent Systems: AAMAS 2018, Stockholm, Sweden, 10-15 July 2018, volume 3 of 3》 - International Conference on Autonomous Agents and Multiagent Systems - 2018, - 1941～1943 - 共3页

摘要：We introduce a novel framework to model limited lookahead in congestion games. Intuitively, the players enter the game sequentially and choose an optimal action under the assumption that the k - 1 sub...

关键词： Congestion games | Limited backward induction | Subgame-perfect equilibrium | Greedy best-response

NSTL主题词： Tie | lookahead | Clidemia hirta | Game theory

5. XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure NSTL国家科技图书文献中心

Hans L. Bodlaender | Carla Groenland ... - 《Algorithmica》 - 2025,87(4) - 465～506 - 共42页

摘要：Abstract In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, ...

6. Approximating Pathwidth for Graphs of Small Treewidth NSTL国家科技图书文献中心

Carla Groenland | Gwenael Joret ... - 《Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms: SODA 2021, Alexandria, Virginia, USA, 10-13 January 2021, volume 3 of 4》 - Annual ACM-SIAM Symposium on Discrete Algorithms - 2021, - 1965～1976 - 共12页

摘要：We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t√(log t)). This is the first algorithm to achieve an f(t)-appro...

NSTL主题词： Small

7. Judgment Aggregation under Issue Dependencies NSTL国家科技图书文献中心

Marco Costantini | Carla Groenland ... - 《Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence and the Twenty-Eighth Innovative Applications of Artificial Intelligence Conference: 12-17 February 2016, Phoenix, Arizona, USA, v.1》 - AAAI Conference on Artificial Intelligence - 2016, - 468～474 - 共7页

摘要：We introduce a new family of judgment aggregation rules, called the binomial rules, designed to account for hidden dependencies between some of the issues being judged. To place them within the landsc...

8. Quasi-Linear Distance Query Reconstruction for Graphs of Bounded Treelength OA开放获取

Paul Bastide | Carla Groenland - 《LIPIcs : Leibniz International Proceedings in Informatics》 - 2024,321 - 1～11 - 共11页

摘要：In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the s...

关键词： Distance Reconstruction | Randomized Algorithm | Treelength

9. A Polynomial Time Algorithm for Steiner Tree When Terminals Avoid a Rooted K₄-Minor OA开放获取

Carla Groenland | Jesper Nederlof ... - 《LIPIcs : Leibniz International Proceedings in Informatics》 - 2024,321 - 1～17 - 共17页

摘要：We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that th...

摘要：A classic model to study strategic decision making in multi-agent systems is the normal-form game. This model can be generalised to allow for an infinite number of pure strategies leading to continuou...

关键词： Game theory | Continuous game | Multi-objective | Nash equilibria

摘要：We introduce a new model of indeterminacy in graphs: instead of specifying all the edges of the graph, the input contains all triples of vertices that form a connected subgraph. In general, different ...

关键词： Algorithms | Graph reconstruction | Indeterminacy | Uncertainty | Connected subgraphs

摘要：Let XNLP be the class of parameterized prob-lems such that an instance of size $n$ with parameter...

关键词： Computer science | Processor scheduling | Bandwidth | Complexity theory

摘要：We introduce a novel framework to model limited lookahead in congestion games. Intuitively, the players enter the game sequentially and choose an optimal action under the assumption that the k - 1 sub...

关键词： Congestion games | Limited backward induction | Subgame-perfect equilibrium | Greedy best-response

NSTL主题词： Tie | lookahead | Clidemia hirta | Game theory

摘要：Abstract In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, ...

摘要：We describe a polynomial-time algorithm which, given a graph G with treewidth t, approximates the pathwidth of G to within a ratio of O(t√(log t)). This is the first algorithm to achieve an f(t)-appro...

NSTL主题词： Small

摘要：We introduce a new family of judgment aggregation rules, called the binomial rules, designed to account for hidden dependencies between some of the issues being judged. To place them within the landsc...

摘要：In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices u and v, the oracle returns the s...

关键词： Distance Reconstruction | Randomized Algorithm | Treelength

摘要：We study a special case of the Steiner Tree problem in which the input graph does not have a minor model of a complete graph on 4 vertices for which all branch sets contain a terminal. We show that th...

关键词： Steiner tree | rooted minor

4008-161-200 800-990-8900

国家科技图书文献中心