We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the online preemptive and the incremental graphmodels. In the Online ...
详细信息
We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the online preemptive and the incremental graphmodels. In the Online Preemptive model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded, and all rejections are permanent. In this model, the complexity of the problems is settled for deterministic algorithms (McGregor, in: Proceedings of the 8thinternationalworkshop on approximation, randomization and combinatorial optimization problems, and proceedings of the 9thinternational conference on randomization and computation: algorithms and techniques, APPROX'05/RANDOM'05, Springer, Berlin, pp. 170-181, 2005;Varadaraja, in: Automata, languages and programming: 38thinternational colloquium, ICALP 2011, Zurich, Switzerland, proceedings, part I, pp. 379-390, 2011. https://***/10.1007/978-3-642-22006-7_32). Epstein et al. (in: 30thinternational symposium on theoretical aspects of computer science, STACS 2013, Kiel, Germany, pp. 389-399, 2013. https://***/10.4230/***.2013.389) gave a 5.356-competitive randomized algorithm for MWM, and also proved a lower bound on the competitive ratio of (1+ln2)approximate to 1.693 for MCM. the same lower bound applies for MWM. In the Incremental graph model, at each step an edge is added to the graph, and the algorithm is supposed to quickly update its current matching. Gupta (in: 34thinternational conference on foundation of software technology and theoretical computer science, FSTTCS 2014, 15-17 Dec 2014, New Delhi, India, pp. 227-239, 2014. https://***/10.4230/***.2014.227) proved that for any E <= 1/2, there exists an algorithm that maintains a (1+E)-approximate MCM for an incremental bipartite graph in an amortized update
the proceedings contain 10 papers. the special focus in this conference is on algorithms and models for the webgraph. the topics include: High-ordered random walks and generalized laplacians on hypergraphs;detecting ...
ISBN:
(纸本)9783642212857
the proceedings contain 10 papers. the special focus in this conference is on algorithms and models for the webgraph. the topics include: High-ordered random walks and generalized laplacians on hypergraphs;detecting the structure of social networks using (α,β)-communities;latent clustering on graphs with multiple edge types;quick detection of top-k personalized pagerank lists;rank-based models of network structure and the discovery of content;1-local 33/24-competitive algorithm for multicoloring hexagonal graphs;modeling social networks through user background and behavior;dirichlet pagerank and trust-based ranking algorithms.
web crawlers are used by internet search engines to gather information about the webgraph. In this paper we investigate a simple process which models such software by walking around the vertices of a graph. Once init...
详细信息
We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the online preemptive and the incremental graphmodels. In the Online ...
详细信息
ISBN:
(数字)9783319623894
ISBN:
(纸本)9783319623887
We study the Maximum Cardinality Matching (MCM) and the Maximum Weight Matching (MWM) problems, on trees and on some special classes of graphs, in the online preemptive and the incremental graphmodels. In the Online Preemptive model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded, and all rejections are permanent. In this model, the complexity of the problems is settled for deterministic algorithms (McGregor, in: Proceedings of the 8thinternationalworkshop on approximation, randomization and combinatorial optimization problems, and proceedings of the 9thinternational conference on randomization and computation: algorithms and techniques, APPROX'05/RANDOM'05, Springer, Berlin, pp. 170-181, 2005;Varadaraja, in: Automata, languages and programming: 38thinternational colloquium, ICALP 2011, Zurich, Switzerland, proceedings, part I, pp. 379-390, 2011. https://***/10.1007/978-3-642-22006-7_32). Epstein et al. (in: 30thinternational symposium on theoretical aspects of computer science, STACS 2013, Kiel, Germany, pp. 389-399, 2013. https://***/10.4230/***.2013.389) gave a 5.356-competitive randomized algorithm for MWM, and also proved a lower bound on the competitive ratio of (1+ln2)approximate to 1.693 for MCM. the same lower bound applies for MWM. In the Incremental graph model, at each step an edge is added to the graph, and the algorithm is supposed to quickly update its current matching. Gupta (in: 34thinternational conference on foundation of software technology and theoretical computer science, FSTTCS 2014, 15-17 Dec 2014, New Delhi, India, pp. 227-239, 2014. https://***/10.4230/***.2014.227) proved that for any E <= 1/2, there exists an algorithm that maintains a (1+E)-approximate MCM for an incremental bipartite graph in an amortized update
Generative graphmodels play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. the explanatory power o...
详细信息
ISBN:
(数字)9783319928715
ISBN:
(纸本)9783319928715;9783319928708
Generative graphmodels play an important role in network science. Unlike real-world networks, they are accessible for mathematical analysis and the number of available networks is not limited. the explanatory power of results on generative models, however, heavily depends on how realistic they are. We present a framework that allows for a systematic evaluation of generative network models. It is based on the question whether real-world networks can be distinguished from generated graphs with respect to certain graph parameters. As a proof of concept, we apply our framework to four popular random graphmodels (Erdos-Renyi, Barabasi-Albert, Chung-Lu, and hyperbolic random graphs). Our experiments for example show that all four models are bad representations for Facebook's social networks, while Chung-Lu and hyperbolic random graphs are good representations for other networks, with different strengths and weaknesses.
Binomial random intersection graphs can be used as parsimonious statistical models of large and sparse networks, with one parameter for the average degree and another for transitivity, the tendency of neighbours of a ...
详细信息
the proceedings contain 10 papers. the topics discussed include: a spectral algorithm for computing social balance;high-ordered random walks and generalized Laplacians on hypergraphs;latent clustering on graphs with m...
ISBN:
(纸本)9783642212857
the proceedings contain 10 papers. the topics discussed include: a spectral algorithm for computing social balance;high-ordered random walks and generalized Laplacians on hypergraphs;latent clustering on graphs with multiple edge types;quick detection of top-k personalized pagerank lists;rank-based models of network structure and the discovery of content;1-local 33/24-competitive algorithm for multicoloring hexagonal graphs;modeling social networks through user background and behavior;dirichlet pagerank and trust-based ranking algorithms;and efficient generation of networks with given expected degrees.
Research on self-organizing networks, especially in the context of the webgraph, holds great promise to understand the complexity that underlies many social systems. We argue that models of social network structure s...
详细信息
ISBN:
(纸本)9783642212864
Research on self-organizing networks, especially in the context of the webgraph, holds great promise to understand the complexity that underlies many social systems. We argue that models of social network structure should begin to consider how structure arises from the "content" of networks, a term we use to describe attributes of network actors that are independent of their structural position, such as skill, intelligence, or wealth. We propose a rank model of how content (operationalized as attribute rank relative to other individuals) may change amongst agents over time within a stochastic system. We then propose a model of network self-organization based on this rank model. Finally, we demonstrate how one may make inferences about the content of networks when attributes are unobserved, but network structures are readily measured. this approach holds promise to enhance our study of social interactions within the webgraph and in complex social networks in general.
the proceedings contain 34 papers. the special focus in this conference is on graph-Based Representations in Pattern Recognition. the topics include: Speeding Up graph Edit Distance Computation through Fast Bipartite ...
ISBN:
(纸本)9783642208430
the proceedings contain 34 papers. the special focus in this conference is on graph-Based Representations in Pattern Recognition. the topics include: Speeding Up graph Edit Distance Computation through Fast Bipartite Matching;two New graph Kernels and Applications to Chemoinformatics;generalized Learning graph Quantization;parallel Graduated Assignment Algorithm for Multiple graph Matching Based on a Common Labelling;smooth Simultaneous Structural graph Matching and Point-Set Registration;automatic Learning of Edit Costs Based on Interactive and Adaptive graph Recognition;exploration of the Labelling Space Given graph Edit Distance Costs;graph Matching Based on Dot Product Representation of graphs;indexing with Well-Founded Total Order for Faster Subgraph Isomorphism Detection;graph Descriptors from B-Matrix Representation;graph Transduction as a Non-cooperative Game;a graph-Based Approach to Feature Selection;spatio-Temporal Extraction of Articulated models in a graph Pyramid;semi-supervised Segmentation of 3D Surfaces Using a Weighted graph Representation;convexity Grouping of Salient Contours;hierarchical Interactive Image Segmentation Using Irregular Pyramids;tiled Top-Down Pyramids and Segmentation of Large Histological Images;segmentation of Similar Images Using graph Matching and Community Detection;automatic Street graph Construction in Sketch Maps;people Re-identification by graph Kernels Methods;dimensionality Reduction for graph of Words Embedding;automatic Labeling of Handwritten Mathematical Symbols via Expression Matching;structure-Based Evaluation Methodology for Curvilinear Structure Detection algorithms;keygraphs for Sign Detection in Indoor Environments by Mobile Phones;classification of graph Sequences Utilizing the Eigenvalues of the Distance Matrices and Hidden Markov models;using Kernels on Hierarchical graphs in Automatic Classification of Designs;entropy versus Heterogeneity for graphs.
the proceedings contain 44 papers. the special focus in this conference is on algorithms and Data Structures. the topics include: Shape segmentation and matching with flow discretization;phylogenetic reconstruction fr...
ISBN:
(纸本)3540405453
the proceedings contain 44 papers. the special focus in this conference is on algorithms and Data Structures. the topics include: Shape segmentation and matching with flow discretization;phylogenetic reconstruction from gene-rearrangement data with unequal gene content;common-deadline lazy bureaucrat scheduling problems;bandwidth-constrained allocation in grid computing;algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection;fast algorithms for a class of temporal range queries;optimal worst-case operations for implicit cache-oblivious search trees;extremal configurations and levels in pseudoline arrangements;fast relative approximation of potential fields;integrated prefetching and caching with read and write requests;online seat reservations via offline seating arrangements;routing and call control algorithms for ring networks;algorithms and models for railway optimization;approximation of rectilinear Steiner trees with length restrictions on obstacles;cropping-resilient segmented multiple watermarking;on simultaneous planar graph embeddings;approximation algorithm for hotlink assignments in web directories;drawing graphs with large vertices and thick edges;semi-matchings for bipartite graphs and load balancing;sorting circular permutations by reversal;an improved bound on Boolean matrix multiplication for highly clustered data;real two dimensional scaled matching;the zigzag path of a pseudo-triangulation;improved approximation algorithms for the quality of service Steiner tree problem;a model for analyzing black-box optimization;on the hausdorff voronoi diagram of point clusters in the plane;significant-presence range queries in categorical data and parameterized complexity of directed feedback set problems in tournaments.
暂无评论