Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
4.1
1.8
Journals
Algorithms
Special Issues
Graph Algorithms and Applications
share announcement

Graph Algorithms and Applications

A special issue of Algorithms (ISSN 1999-4893). This special issue belongs to the section "Combinatorial Optimization, Graph, and Network Algorithms".

Deadline for manuscript submissions: closed (15 December 2020) | Viewed by 20603

Printed Edition Available!
A printed edition of this Special Issue is available here.

Special Issue Editors

Prof. Gabriele Di Stefano

E-Mail Website
Guest Editor
Professor of Computer Science, University of L'Aquila, Italy
Interests: Algorithms; graph theory
Dr. Serafino Cicerone

E-Mail Website
Guest Editor
Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, Palazzo Camponeschi, Piazza Santa Margherita, 2, 67100 L'Aquila, Italy
Interests: distributed algorithms; algorithmic graph theory; algorithm engineering; robust algorithms; algorithms and models for spatial data

Special Issue Information

Dear Colleagues,

The mixture of data in real life exhibits structure or connection property in nature. Typical data include biological data, communication network data, image data, and so on. Graphs provide a natural way to represent and analyze these types of data and their relationships. For instance, more recently, graphs have found new applications in emerging research fields like social network analysis, the design of robust computer network topologies, frequency allocation in wireless networks, and bioinformatics. Unfortunately, the related algorithms usually suffer from high computational complexity, and some of them are even NP-complete problems. Therefore, in recent years, many graph models and optimization algorithms have been proposed to achieve a better balance between efficacy and efficiency.

The aim of this Special Issue is to provide an opportunity for researchers and engineers from both academia and industry to publish their latest and original results on graph models, algorithms, and applications to problems in the real world, with a focus on optimization and computational complexity. The proposed graph algorithms can be of various types, such as exact or approximated, centralized or distributed, static or dynamic, and deterministic or randomized. Suitable implementations and applications of the proposed algorithms are also encouraged.

Prof. Gabriele Di Stefano
Dr. Serafino Cicerone
Guest Editors

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Algorithms is an international peer-reviewed open access monthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 1600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • The design and analysis of sequential, randomized, or parameterized graph algorithms
  • Distributed graph and network algorithms
  • Graph theory with algorithmic applications
  • The computational complexity of graph and network problems
  • The experimental evaluation of graph algorithms.

Benefits of Publishing in a Special Issue

  • Ease of navigation: Grouping papers by topic helps scholars navigate broad scope journals more efficiently.
  • Greater discoverability: Special Issues support the reach and impact of scientific research. Articles in Special Issues are more discoverable and cited more frequently.
  • Expansion of research network: Special Issues facilitate connections among authors, fostering scientific collaborations.
  • External promotion: Articles in Special Issues are often promoted through the journal's social media, increasing their visibility.
  • e-Book format: Special Issues with more than 10 articles can be published as dedicated e-books, ensuring wide and rapid dissemination.

Further information on MDPI's Special Issue polices can be found here.

Published Papers (7 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Editorial

Jump to: Research

3 pages, 179 KiB  
Editorial
Special Issue on “Graph Algorithms and Applications”
by Serafino Cicerone and Gabriele Di Stefano
Algorithms 2021, 14(5), 150; https://doi.org/10.3390/a14050150 - 10 May 2021
Viewed by 2347
Abstract
The mixture of data in real life exhibits structure or connection property in nature. Typical data include biological data, communication network data, image data, etc. Graphs provide a natural way to represent and analyze these types of data and their relationships. For instance, [...] Read more.
The mixture of data in real life exhibits structure or connection property in nature. Typical data include biological data, communication network data, image data, etc. Graphs provide a natural way to represent and analyze these types of data and their relationships. For instance, more recently, graphs have found new applications in solving problems for emerging research fields such as social network analysis, design of robust computer network topologies, frequency allocation in wireless networks, and bioinformatics. Unfortunately, the related algorithms usually suffer from high computational complexity, since some of these problems are NP-hard. Therefore, in recent years, many graph models and optimization algorithms have been proposed to achieve a better balance between efficacy and efficiency. The aim of this Special Issue is to provide an opportunity for researchers and engineers from both academia and the industry to publish their latest and original results on graph models, algorithms, and applications to problems in the real world, with a focus on optimization and computational complexity. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)

Research

Jump to: Editorial

14 pages, 344 KiB  
Article
A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2
by Serafino Cicerone
Algorithms 2021, 14(4), 105; https://doi.org/10.3390/a14040105 - 25 Mar 2021
Cited by 2 | Viewed by 2198
Abstract
Cicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. The defined graphs represent a generalization of the well [...] Read more.
Cicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. The defined graphs represent a generalization of the well known distance-hereditary graphs, which actually correspond to 1-distance-hereditary graphs. In this paper we make a step forward in the study of these new graphs by providing characterizations for the class of all the k-distance-hereditary graphs such that k<2. The new characterizations are given in terms of both forbidden subgraphs and cycle-chord properties. Such results also lead to devise a polynomial-time recognition algorithm for this kind of graph that, according to the provided characterizations, simply detects the presence of quasi-holes in any given graph. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)
►▼ Show Figures

Figure 1

14 pages, 497 KiB  
Article
Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
by Chuan-Min Lee
Algorithms 2021, 14(1), 22; https://doi.org/10.3390/a14010022 - 13 Jan 2021
Cited by 6 | Viewed by 2492
Abstract
This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly [...] Read more.
This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the {k}-clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)
►▼ Show Figures

Figure 1

10 pages, 392 KiB  
Article
Efficient Approaches to the Mixture Distance Problem
by Justie Su-Tzu Juan, Yi-Ching Chen, Chen-Hui Lin and Shu-Chuan Chen
Algorithms 2020, 13(12), 314; https://doi.org/10.3390/a13120314 - 28 Nov 2020
Cited by 2 | Viewed by 1988
Abstract
The ancestral mixture model, an important model building a hierarchical tree from high dimensional binary sequences, was proposed by Chen and Lindsay in 2006. As a phylogenetic tree (or evolutionary tree), a mixture tree created from ancestral mixture models, involves the inferred evolutionary [...] Read more.
The ancestral mixture model, an important model building a hierarchical tree from high dimensional binary sequences, was proposed by Chen and Lindsay in 2006. As a phylogenetic tree (or evolutionary tree), a mixture tree created from ancestral mixture models, involves the inferred evolutionary relationships among various biological species. Moreover, it contains the information of time when the species mutates. The tree comparison metric, an essential issue in bioinformatics, is used to measure the similarity between trees. To our knowledge, however, the approach to the comparison between two mixture trees is still unknown. In this paper, we propose a new metric named the mixture distance metric, to measure the similarity of two mixture trees. It uniquely considers the factor of evolutionary times between trees. If we convert the mixture tree that contains the information of mutation time of each internal node into a weighted tree, the mixture distance metric is very close to the weighted path difference distance metric. Since the converted mixture tree forms a special weighted tree, we were able to design a more efficient algorithm to calculate this new metric. Therefore, we developed two algorithms to compute the mixture distance between two mixture trees. One requires O(n2) and the other requires O(nh1h2) computational time with O(n) preprocessing time, where n denotes the number of leaves in the two mixture trees, and h1 and h2 denote the heights of these two trees. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)
►▼ Show Figures

Figure 1

23 pages, 414 KiB  
Article
On Multidimensional Congestion Games
by Vittorio Bilò, Michele Flammini, Vasco Gallotti and Cosimo Vinci
Algorithms 2020, 13(10), 261; https://doi.org/10.3390/a13100261 - 15 Oct 2020
Cited by 3 | Viewed by 3032
Abstract
We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d+1 clusters C0,C1,…,Cd. Players in C0 have full information about all the other participants [...] Read more.
We introduce multidimensional congestion games, that is, congestion games whose set of players is partitioned into d+1 clusters C0,C1,…,Cd. Players in C0 have full information about all the other participants in the game, while players in Ci, for any 1≤i≤d, have full information only about the members of C0∪Ci and are unaware of all the others. This model has at least two interesting applications: (i) it is a special case of graphical congestion games induced by an undirected social knowledge graph with independence number equal to d, and (ii) it represents scenarios in which players have a type and the level of competition they experience on a resource depends on their type and on the types of the other players using it. We focus on the case in which the cost function associated with each resource is affine and bound the price of anarchy and stability as a function of d with respect to two meaningful social cost functions and for both weighted and unweighted players. We also provide refined bounds for the special case of d=2 in presence of unweighted players. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)
►▼ Show Figures

Figure A1

20 pages, 378 KiB  
Article
Multi-Winner Election Control via Social Influence: Hardness and Algorithms for Restricted Cases
by Mohammad Abouei Mehrizi and Gianlorenzo D'Angelo
Algorithms 2020, 13(10), 251; https://doi.org/10.3390/a13100251 - 2 Oct 2020
Cited by 5 | Viewed by 2855
Abstract
Nowadays, many political campaigns are using social influence in order to convince voters to support/oppose a specific candidate/party. In election control via social influence problem, an attacker tries to find a set of limited influencers to start disseminating a political message in a [...] Read more.
Nowadays, many political campaigns are using social influence in order to convince voters to support/oppose a specific candidate/party. In election control via social influence problem, an attacker tries to find a set of limited influencers to start disseminating a political message in a social network of voters. A voter will change his opinion when he receives and accepts the message. In constructive case, the goal is to maximize the number of votes/winners of a target candidate/party, while in destructive case, the attacker tries to minimize them. Recent works considered the problem in different models and presented some hardness and approximation results. In this work, we consider multi-winner election control through social influence on different graph structures and diffusion models, and our goal is to maximize/minimize the number of winners in our target party. We show that the problem is hard to approximate when voters’ connections form a graph, and the diffusion model is the linear threshold model. We also prove the same result considering an arborescence under independent cascade model. Moreover, we present a dynamic programming algorithm for the cases that the voting system is a variation of straight-party voting, and voters form a tree. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)
10 pages, 401 KiB  
Article
Graph Planarity by Replacing Cliques with Paths
by Patrizio Angelini, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen Kobourov, Giuseppe Liotta, Alfredo Navarra and Alessandra Tappini
Algorithms 2020, 13(8), 194; https://doi.org/10.3390/a13080194 - 13 Aug 2020
Cited by 7 | Viewed by 3921
Abstract
This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h [...] Read more.
This paper introduces and studies the following beyond-planarity problem, which we call h-Clique2Path Planarity. Let G be a simple topological graph whose vertices are partitioned into subsets of size at most h, each inducing a clique. h-Clique2Path Planarity asks whether it is possible to obtain a planar subgraph of G by removing edges from each clique so that the subgraph induced by each subset is a path. We investigate the complexity of this problem in relation to k-planarity. In particular, we prove that h-Clique2Path Planarity is NP-complete even when h=4 and G is a simple 3-plane graph, while it can be solved in linear time when G is a simple 1-plane graph, for any value of h. Our results contribute to the growing fields of hybrid planarity and of graph drawing beyond planarity. Full article
(This article belongs to the Special Issue Graph Algorithms and Applications)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-7
Back to TopTop