-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathijnc-apdcm-2012.tex
142 lines (103 loc) · 4.39 KB
/
ijnc-apdcm-2012.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
\documentclass[twoside]{article}
\input{preamble.tex}
\usepackage{IJNC}
\setcounter{page}{501}
\newcommand{\jvolume}{X}
\newcommand{\jnumber}{Y}
\newcommand{\jmonth}{January}
\newcommand{\jyear}{20XX}
% title
\newcommand{\jtitle}{A General Purpose Automata for Distributed Graph Algorithms}
% running title for header
\newcommand{\jrunningtitle}{A General Purpose Automata}
\pagestyle{plain}
\begin{document}
\thispagestyle{empty}
\copyrightheader
\begin{center}
% print title
\jtitle
\vspace{20pt}
J. Paul Daigle
\vspace{2pt}
Department of Computer Science, Georgia State University\\
Atlanta, GA, 30303, USA
\vspace{10pt}
%and
%
\vspace{10pt}
Sushil K. Prasad
\vspace{2pt}
Department of Computer Science, Georgia State University\\
Atlanta, GA, 30303, USA
\vspace{10pt}
%and
%
%\vspace{10pt}
%THIRD AUTHOR
%
%\vspace{2pt}
%Group, Laboratory, Address\\
%City, State ZIP, Country
\vspace{20pt}
\publisher{(received date)}{(revised date)}{(accepted date)}{Editor's name}
%\publisherA{(received date)}{(revised date)}{(revised date)}{(accepted date)}{Editor's name}
\end{center}
\begin{abstract}
We present an automata for a compute node in a message passing model which allows a distributed computer to approximate solutions for three NP-Complete graph problems. Our algorithm for the Vertex Cover Problem uses $O(\log{\Delta)}$ communication rounds to find a 2-approximate solution. Our edge coloring algorithm is also 2-approximate and resolves in $O(\Delta)$ rounds, and we find a correct strong edge coloring of a symmetric digraph in $O(\Delta)$ rounds. All three algorithms require only one hop information to find correct solutions.
\keywords{Distributed Algorithms, Vertex Cover, Edge Coloring, Strong Edge Coloring}
\end{abstract}
\section{Introduction}
\input{secs/sec-introduction}
\subsection{Definitions}
\input{defs/def-mvc}
\input{defs/def-mwvc}
\input{defs/def-edge-color}
\input{defs/def-strong-directed-edge-color}
Figure~\ref{fig:edge-colorings} illustrates edge coloring.
\input{figs/fig-edge-colorings}
\subsection{Prior Work}
\subsubsection{Vertex Cover}
\input{secs/sec-prior-vertex}
\subsubsection{Edge Coloring}
\input{secs/sec-prior-edge}
\subsection{Organization}
Our model and framework are presented in Section~\ref{sec:framework}. In Section~\ref{sec:dgmm-description} we describe the sequential algorithm of Gonzalez and show how the framework is applied to produce the distributed algorithm. In Section~\ref{ssb:algorithms-dgmm-performance} we provide a detailed proof of its performance bounds. Our experimental setup and results are described in Section~\ref{sec:vertex-experiment}.
Section~\ref{sec:edge-coloring-problems} covers the algorithms for edge coloring and strong directed edge coloring. Section~\ref{sec:dimaed-description} describes DiMaEd, our edge coloring algorithm. Section~\ref{sec:dimaed-correct} discusses the running time and correctness of DiMaEd. Our experimental results for the edge coloring problem are in Section~\ref{sec:dimaed-experiments}. Section~\ref{sec:dima2ed-description} introduces DiMa2ed, our algorithm for strong edge coloring. We discuss the running time and correctness of DiMa2ed in Section~\ref{sec:dima2ed-correct}. We present limited experimental results for DiMa2ed in Section~\ref{sub:experiment-erdren-direct}.
\section{The Model and Automata}
\label{sec:framework}
\subsection{The Message Passing Model}
\input{secs/sec-message-passing}
\subsection{The Matching Automata}
\input{secs/sec-automata}
\section{The Vertex Cover Problem}
\subsection{Algorithm}
\input{algs/alg-dgmm.tex}
\input{secs/sec-dgmm-description}
\subsection{Analysis}
\input{secs/sec-dgmm-analysis}
\subsection{Experimental Design and Results}
\input{secs/sec-vertex-experiment}
\section{Distance One Edge Coloring Problem}
\label{sec:edge-coloring-problems}
\subsection{Description}
\input{algs/alg-edge-color}
\input{secs/sec-dimaed-description}
\subsection{Analysis}
\input{secs/sec-dimaed-correct}
\subsection{Experimental Results}
\input{secs/sec-dimaed-experiments}
\section{Distance 2 Directed Edge Coloring Problem}
\subsection{Description}
\input{secs/sec-dima2ed-description}
\input{algs/alg-dima2ed}
\subsection{Analysis}
\input{secs/sec-dima2ed-correct}
\subsection{Experimental Results}
\label{sub:experiment-erdren-direct}
\input{secs/sec-experiment-erdren-direct}
\section{Discusion}
\input{secs/sec-discussion}
\bibliographystyle{plain}
\bibliography{ijnc-apdcm-2012}
\end{document}