Bounded Asymmetry in Road Networks.
Ontology highlight
ABSTRACT: Road networks are a classical stage for applications in network science and graph theory. Meanwhile, many combinatorial problems that arise in road networks are computationally intractable. Thus, an attractive way of tackling them is through efficient heuristics with provable performance guarantees, better known as approximation algorithms. This motivates the intersection of algorithm design with the aforementioned fields. Specifically, identifying measures that characterize graphs and exploiting them in the design of algorithms may yield practical heuristics with rigorous mathematical justification. Herein, we propose a new graph measure, namely the asymmetry factor ΔG of a directed graph G, with immediate algorithmic results via a symmetrization procedure and the black box use
SUBMITTER: Martinez Mori JC
PROVIDER: S-EPMC6697698 | biostudies-literature | 2019 Aug
REPOSITORIES: biostudies-literature
ACCESS DATA